用c++实现二分查找,查找元素x出现的位置及查询次数
时间: 2023-05-29 15:05:09 浏览: 150
以下是用C语言实现二分查找的示例代码,其中包含了查找元素x出现的位置及查询次数的功能:
```
#include <stdio.h>
int binarySearch(int arr[], int left, int right, int x, int* count) {
while (left <= right) {
(*count)++;
int mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 如果未找到,返回-1
}
int main() {
int arr[] = {2, 5, 6, 9, 10, 12, 15, 18, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 15;
int count = 0;
int result = binarySearch(arr, 0, n - 1, x, &count);
if (result == -1) {
printf("元素 %d 未找到\n", x);
} else {
printf("元素 %d 出现的位置是 %d\n", x, result);
}
printf("查询次数为 %d\n", count);
return 0;
}
```
在上面的代码中,我们定义了一个函数`binarySearch`,它接收一个整数数组`arr`、数组的左右边界`left`和`right`、要查找的元素`x`以及一个指向整数的指针`count`,用于记录查询次数。函数返回值为要查找的元素在数组中的位置,如果未找到则返回-1。
函数中使用了一个while循环,不断缩小查找范围,直到找到要查找的元素或者查找范围为空。在每次循环中,我们计数一次查询次数,然后计算中间位置`mid`,如果`arr[mid]`等于要查找的元素`x`,则直接返回`mid`。如果`arr[mid]`小于`x`,则说明要查找的元素在右半部分,将左边界`left`更新为`mid + 1`。如果`arr[mid]`大于`x`,则说明要查找的元素在左半部分,将右边界`right`更新为`mid - 1`。
在`main`函数中,我们声明了一个整数数组`arr`,并计算数组的长度`n`。我们要查找的元素是`x=15`,然后调用`binarySearch`函数进行查找,并将查询次数记录在`count`变量中。如果找到了要查找的元素,就输出它在数组中的位置,否则输出未找到的提示。最后输出查询次数。