c语言求二分查找的比较次数
时间: 2023-08-10 10:40:56 浏览: 57
以下是使用二分查找算法查找有序数组中某个元素的 C 语言代码实现,同时记录了比较次数:
```c
int binary_search(int arr[], int left, int right, int target, int *compare_count) {
while (left <= right) {
int mid = left + (right - left) / 2;
(*compare_count)++; // 每一次比较都增加计数器
if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
```
其中,`arr` 是有序数组,`left` 和 `right` 是要查找的区间范围,`target` 是要查找的目标元素,`compare_count` 是一个指向计数器的指针,在每次比较时都会增加计数器的值。
例如,如果要查找数组 `arr` 中是否包含元素 `target`,可以这样调用该函数:
```c
int arr[] = {1, 3, 5, 7, 9};
int left = 0, right = 4, target = 5, compare_count = 0;
int index = binary_search(arr, left, right, target, &compare_count);
printf("目标元素 %d 在数组中的索引是 %d,比较次数是 %d\n", target, index, compare_count);
```
输出结果将会是:
```
目标元素 5 在数组中的索引是 2,比较次数是 2
```
因为在这个例子中,最多只需要比较两次就找到了目标元素,因此比较次数是 2。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)