C++ 折半查找（二分查找）

总结归纳

代码实践

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

#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;
}