二分查找

• 建立在数组有序的基础上
• key 与 a[mid] 比较来限界
• 查找过程可以细分为四种情况
  • 在范围外，查找不到
  • 特殊情况，边界值
  • 一般情况，中间值
  • 在范围内，查找不到

#include <iostream>

using namespace std;

// 二分查找
int binarySearch(const int *a, int key, int low, int high) {
    // 在范围外，查找不到
    if (key < a[low] || key > a[high]) return -1;

    // 特殊情况，边界值
    if (key == a[high]) return high;
    if (key == a[low]) return low;

    // 一般情况，中间值
    while (low <= high) { // while中这一关系可能改变，改变说明找不到
        int mid = (low + high) / 2;
        if (key > a[mid]) low = mid + 1;
        else if (key < a[mid]) high = mid - 1;
        else return mid;
    }

    return -1; // 在范围内，查找不到
}

void printArray(const int *a, int len) {
    for (int i = 0; i < len; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int a[10] = {0, 16, 24, 35, 47, 59, 62, 73, 88, 99};
    printArray(a, 10);
    cout << "查找：";
    int key;
    cin >> key;
    cout << "位置：" << binarySearch(a, key, 0, 9);
    return 0;
}

0 16 24 35 47 59 62 73 88 99 
查找：24
位置：2