- 建立在数组有序的基础上
- 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
