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;
}