C语言实现折半查找法（二分法）

简介

折半查找法，也称二分法，是一种高效的查找算法。它适用于有序数组，具体实现方法是先确定中间位置元素，然后与查找元素进行比较，根据比较结果选择剩余部分继续查找，直到找到或未找到。

实现步骤

以下是实现折半查找法的具体步骤：

1. 将查找范围的下标low和up分别设为数组下标的最小值和最大值，即low=0，up=n-1，其中n为数组元素个数。
2. 计算mid，即中间位置的下标，即mid=(low+up)/2。
3. 用待查找元素与中间位置元素进行比较，如果两者相等，返回mid；如果待查找元素小于中间位置元素，则继续在前一半查找，即将up设为mid-1；如果待查找元素大于中间位置元素，则继续在后一半查找，即将low设为mid+1。
4. 重复执行步骤2和步骤3，直到找到待查找元素或者查找范围为空，此时返回-1表示未找到。

示例说明

以下是两个示例说明：

示例1

给定有序数组a={1,2,3,4,5}，要查找元素key=4。

按照上述步骤进行折半查找：

1. low=0，up=4，mid=2，a[mid]=3，key>a[mid]，所以在后一半查找。
2. low=3，up=4，mid=3，a[mid]=4，key=a[mid]，找到了，返回mid=3。

因此，4在数组a中的下标为3。

示例2

给定有序数组a={1,2,3,4,5}，要查找元素key=6。

按照上述步骤进行折半查找：

1. low=0，up=4，mid=2，a[mid]=3，key>a[mid]，所以在后一半查找。
2. low=3，up=4，mid=3，a[mid]=4，key<a[mid]，所以在前一半查找。
3. low=3，up=2，查找范围为空，返回-1表示未找到。

因此，6不在数组a中，返回-1表示未找到。

代码实现

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

其中，参数a为有序数组，n为数组元素个数，key为待查找元素。函数返回找到的元素下标，或者-1表示未找到。