[C++知识库]C++ 二分查找

总结归纳

1. 二分查找的时间复杂度：O(logn) 。
2. 二分查找需要线性表有序，对于静态线性表，可以先使用 C++ 的标准库函数 sort() 或 C 语言的标准库函数 qsort() 进行排序，再进行查找。在高校的机试考试中，不必重写一个排序算法，直接调接口即可。
3. 二分查找的过程： low 指针指向最左边，high 指针指向最右边，每次判断中间数据 (low + high) / 2 是否等于要查找的值，若中间值小于要查找的值，意味着查找值位于中间点右侧，令 low = mid + 1，缩小一半的查找空间；若中间值大于要查找的值，意味着查找值位于中间点左侧，令 high = mid - 1。
4. C/C++语法中，a / b 结果是向下取整，举例说明：5 / 2 = 2。

代码实践

/*
二分查找（折半查找）
*/

#include <algorithm> // C++标准库 sort(起始地址，结束地址，牌序方式(不设置则默认从小到大))
#include <iostream>

#include <stdlib.h> // C语言标准库 qsort(起始地址，长度，数据大小，比较方式)
#include <time.h>

using namespace std;

typedef int ElemType;

struct List {
    ElemType *data;
    int len;
};

// 初始化
void InitList(List &L, int length) {
    L.len = length;
    L.data = (ElemType *)malloc(sizeof(ElemType) * L.len);
    srand(time(NULL));
    for (int i = 0; i < L.len; i++) {
        L.data[i] = rand() % 100; // 随机生成
    }
}

// 遍历
void Print(List L) {
    for (int i = 0; i < L.len; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

// 二分查找
int BinarySearch(List L, ElemType key) {
    int low = 0, high = L.len - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.data[mid] == key) {
            return mid + 1; // mid为数组下标，从0开始
        } else if (L.data[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 比较方式，固定格式
int compare(const void *left, const void *right) {
    return (*(ElemType *)left - *(ElemType *)right); //升序
    // return (*(ElemType*)right - *(ElemType*)left); //降序
}

int main() {
    List L;
    ElemType key;
    int pos; // 查找位置
    InitList(L, 10);
    Print(L);

    sort(L.data, L.data + L.len); // C++标准库排序方法
    // qsort(L.data, 10, sizeof(ElemType), compare); // C语言标准库排序方法
    Print(L);

    cout << "输入查找数值：" << endl;
    cin >> key;

    pos = BinarySearch(L, key);
    if (pos == -1) {
        cout << "未查找到" << endl;
    } else {
        cout << "查找到的位置：" << pos << endl;
    }

    return 0;
}