定义一个长度为N的整型有序数组,请定义折半查找函数,并在主函数中调用该折半查找算法实现查找功能,并统计查找过程中数据元素比较次数。
时间: 2024-02-23 22:58:14 浏览: 66
好的,以下是折半查找函数的 C++ 代码实现:
```cpp
int binarySearch(int arr[], int n, int target, int& count) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
count++; // 记录比较次数
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
```
在主函数中,你可以先定义一个长度为N的整型有序数组,然后调用`binarySearch`函数进行查找,同时记录比较次数:
```cpp
int main() {
const int N = 10;
int arr[N] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = 11;
int count = 0;
int index = binarySearch(arr, N, target, count);
if (index != -1) {
cout << "找到了,索引是:" << index << endl;
} else {
cout << "没找到!" << endl;
}
cout << "比较次数:" << count << endl;
return 0;
}
```
注意,`count`参数是通过引用传递的,在函数内部对它的修改会影响到主函数中的值。
阅读全文