二分查找
描述
从小到大输入若干整数（不超过300），以-99999为结束符，然后再输入一个整数x，在前面的整数中用二分查找法查找x，若找到，显示数的下标（即从0开始的序号）；若找不到，显示-1。注意，不应使用别人写的库函数。
输入
若干整数。
输出
一个下标。
输入输出示例
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> nums;
int num;
while (cin >> num && num != -99999) {
nums.push_back(num);
}
int x;
cin >> x;
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == x) {
cout << mid << endl;
return 0;
} else if (nums[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << -1 << endl;
return 0;
}
#include <iostream>
using namespace std;
int binarySearch(int a[], int left, int right, int dest);
int main() {
int a[310];
int i = 0;
int num;
while (cin >> num && num != -99999)
a[i++] = num;
int dest;
cin >> dest;
int idx = binarySearch(a, 0, i - 1, dest);
cout << idx << endl;
return 0;
}
int binarySearch(int a[], int left, int right, int dest) {
while (left <= right) { //只要数组还没空
int midIdx = (left + right) / 2; //就取中间值比较
int mid = a[midIdx];
if (dest > mid) //中间值小了，说明目标数在右边，就把左端右移
left = midIdx + 1;
else if (dest < mid) //中间值大了，说明目标数在左边，就把右端左移
right = midIdx - 1;
else
return midIdx;//找到后就返回
}
return -1;
}
//二分查找必须是有序序列
二分查找（Binary Search），也称为折半查找，是一种常用的查找算法。它将要查找的区间中间位置的元素与所要查找的元素进行比较，如果两个元素相等，则查找成功；如果中间位置的元素大于要查找的元素，则在左半部分区间中继续查找；如果中间位置的元素小于要查找的元素，则在右半部分区间中继续查找。依次类推，直到查找到要查找的元素，或者查找区间缩小为 0。
下面是 C++ 实现二分查找的代码示例：
#include <iostream>
#include <algorithm>
using namespace std;
int binarySearch(int arr[], int n, int x) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int result = binarySearch(arr, n, x);
if (result == -1) {
cout << "Element not found" << endl;
} else {
cout << "Element found at index " << result << endl;
}
return 0;
}
在上面的例子中，我们使用了 while 循环实现了二分查找。算法的时间复杂度是 O(log n)。注意到有时候二分查找可能会溢出，因此在计算 mid 时需要用 left + (right – left) / 2 替换 (left + right) / 2。