【C】顺序数组的二分查找

关键函数

int binarySearch(int arr[],int n,int k){
    int low=0,mid,high=n-1;
    while(low<=high){
        mid = (low + high)/2;
        if (k==arr[mid]){
            return mid;
        }
        if (k<arr[mid]){
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return -1;
}

完整程序

#include<stdio.h>
int binarySearch(int arr[],int n,int k){
    int low=0,mid,high=n-1;
    while(low<=high){
        mid = (low + high)/2;
        if (k==arr[mid]){
            return mid;
        }
        if (k<arr[mid]){
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return -1;
}
int main(){
    int n=10,k;
    int a[10]={0,1,3,5,7,8,11,15,22,32};
    printf("请输入要查找的数据：");
    scanf("%d",&k);
    int ans=binarySearch(a,n,k);
    if(ans==-1){
        printf("查找失败，数组中没有%d",k);
    }
    else{
        printf("查找成功，%d的下标是%d",k,ans);
    }
    return 0;
}

ChatGPT的解释

这是一个用于在有序整数数组中执行二分查找的C语言函数。二分查找是一种高效的查找算法，它适用于有序数组，并通过将搜索范围逐渐缩小一半来快速定位目标元素。下面是对该函数的解释：

int binarySearch(int arr[], int n, int k) {
    int low = 0;          // 搜索范围的起始索引
    int mid;              // 中间索引
    int high = n - 1;     // 搜索范围的结束索引

    while (low <= high) {
        mid = (low + high) / 2;  // 计算中间索引

        if (k == arr[mid]) {     // 如果目标元素等于中间元素，找到了目标，返回其索引
            return mid;
        }
        if (k < arr[mid]) {      // 如果目标元素小于中间元素，将搜索范围缩小到左半部分
            high = mid - 1;
        } else {                  // 如果目标元素大于中间元素，将搜索范围缩小到右半部分
            low = mid + 1;
        }
    }

    // 如果循环结束仍未找到目标元素，返回-1表示未找到
    return -1;
}

函数的参数说明：

arr[]：有序整数数组，要在其中执行二分查找。
n：数组中的元素数量。
k：要查找的目标元素。

函数通过在数组中不断缩小搜索范围来查找目标元素。在每一步中，它计算数组的中间索引 mid，然后比较目标元素 k 与中间元素 arr[mid] 的大小关系，以确定应该继续搜索左半部分还是右半部分。如果目标元素等于中间元素，函数返回中间元素的索引，表示找到了目标。如果搜索范围缩小为空，仍未找到目标元素，函数返回-1，表示未找到目标。

这个函数非常高效，因为它每次都将搜索范围缩小一半，而不是线性搜索整个数组，所以在有序数组中查找元素的速度非常快。