输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。并用c++写出其代码
时间: 2024-01-02 07:14:15 浏览: 115
好的,以下是二分查找算法的 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
pair<int, int> binary_search(int arr[], int n, int x) {
int low = 0;
int high = n - 1;
int count = 0;
while (low <= high) {
int mid = (low + high) / 2;
count++;
if (arr[mid] == x) {
return make_pair(mid, count);
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return make_pair(-1, count);
}
int main() {
int n, x;
int arr[1000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cin >> x;
auto result = binary_search(arr, n, x);
if (result.first == -1) {
cout << -1 << " " << result.second << endl;
} else {
cout << result.first << " " << result.second << endl;
}
return 0;
}
```
其中,`arr` 表示非降序排列的整数数组,`n` 表示数组的长度,`x` 表示要查找的数。函数返回一个 `pair` 类型的结果,第一个元素为 `x` 在数组中的下标(从 0 开始),第二个元素为比较次数。
你可以将上述代码复制到你的 C++ 环境中运行,并输入相应的参数进行测试。
阅读全文