C语言算法练习之折半查找的实现

折半查找，也称二分查找，是一种简单而又高效的查找算法。它适用于顺序存储的有序表中进行查找。折半查找的思路是将有序表分成两部分，取中间位置的关键字进行比较，然后根据比较结果确定待查找的关键字可能在哪一部分内，并重复以上步骤，直到找到待查找的关键字位置或确定不存在。

折半查找的实现基于顺序表，需要满足两个条件，一是表中元素按照关键字有序排列，二是表的元素可以随机访问。假设有序表元素存放在数组a[1...n]中，首先要确定待查找元素的区间，即[m,r]，其中m是起始位置，r是终止位置。然后取中间位置mid=(m+r)/2，将待查找关键字key与a[mid]进行比较，如果相等，则查找成功并返回mid；否则如果key小于a[mid]，则在[m,mid-1]区间内继续查找，反之则在[mid+1,r]区间内继续查找，直到找到或区间长度为0为止，查找失败返回-1。

下面给出折半查找的C语言实现代码：

int binarySearch(int a[], int n, int key)
{
    int m = 0, r = n - 1, mid;
    while (m <= r) {
        mid = (m + r) / 2;
        if (a[mid] == key)
            return mid; // 找到，返回下标
        else if (key < a[mid])
            r = mid - 1; // 在左边查找
        else
            m = mid + 1; // 在右边查找
    }
    return -1; // 未找到，返回-1
}

该函数接受一个整型数组a、数组长度n和待查找关键字key作为参数，返回查找结果。变量m、r和mid分别代表待查找区间的起始位置、终止位置和中间位置。while循环中判断区间长度是否为0，如果是则查找失败，返回-1；否则取中间位置mid进行比较。如果a[mid]等于key，则查找成功，返回mid；否则如果key小于a[mid]，说明key可能在[m,mid-1]区间内，将r更新为mid-1，继续查找；否则将m更新为mid+1，继续在[mid+1,r]区间内查找。以上步骤重复直到找到或区间长度为0。

折半查找的时间复杂度为O(log n)，比顺序查找的O(n)要快得多，在大规模数据中表现更加优异。折半查找的优点在于能够快速定位有序表中的元素，适用于数据量较大、有序的场景。在应用中需要注意的是，折半查找要求数据必须按照关键字有序排列，如果数据无序，则需要先进行排序操作，这会增加时间复杂度和空间复杂度。