7-2 二分查找

输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入格式:

输入共三行：
第一行是n值；
第二行是n个整数；
第三行是x值。

输出格式:

输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

输入样例:

4
1 2 3 4
1

输出样例:

0
2

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>int Search(int array[], int size, int target, int *count) {int low = 0;int high = size - 1;int mid;*count = 0;  // 初始化比较次数while (low <= high) {mid = low + (high - low) / 2;(*count)++;if (array[mid] == target) {return mid;  // 返回找到的位置} else if (array[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;  // 没有找到
}int main() {int n, x;scanf("%d", &n);int array[n];for (int i = 0; i < n; i++) {scanf("%d", &array[i]);}scanf("%d", &x);int count;int result = Search(array, n, x, &count);if (result != -1) {printf("%d\n%d\n", result, count);  // 输出位置和比较次数} else {printf("-1\n%d\n", count);  // 输出-1和比较次数}return 0;
}