本题要求实现一个函数，该函数采用二分查找法从一个已经升序排序的数组中，查找某个数k。如果找到k, 输出k所在的数组下标（0~n-1）及比较次数。若k不存在，输出-1和比较次数。 函数接口定义： int Search(int *p, int n, int k,int *Count); void Sort(int *,int n); 其中 p为数组首地址，n为数组长度，k为待查找的数, *Count为比较次数。 函数返回值：如果k在数组中返回其下标值，没找到返回-1。 裁判测试程序样例： #include<stdio.h> #define N 20 int Search(int *pa, int n, int k,int *p); int main() { int a[N],n,cmp,*p=&cmp; int pos,num=0; int i,k; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); scanf("%d",&k); pos=Search(a,n,k,p); printf("%d\n%d\n",pos,cmp); return 0; } /* 请在这里填写答案 */

#include<stdio.h>
#define N 20

int Search(int *p, int n, int k, int *Count);
void Sort(int *p, int n);

int main() {
    int a[N], n, cmp, *p = &cmp;
    int pos, num = 0;
    int i, k;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &k);

    Sort(a, n);  // 先排序

    pos = Search(a, n, k, p);
    printf("%d\n%d\n", pos, cmp);

    return 0;
}

// 二分查找函数
int Search(int *p, int n, int k, int *Count) {
    int low = 0, high = n - 1, mid;

    while (low <= high) {
        (*Count)++;  // 记录比较次数
        mid = (low + high) / 2;
        if (p[mid] == k) {
            return mid;
        } else if (p[mid] > k) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

// 冒泡排序函数，可以替换成其他排序算法
void Sort(int *p, int n) {
    int i, j, tmp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (p[j] > p[j + 1]) {
                tmp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = tmp;
            }
        }
    }
}