C语言折半查找法介绍及使用示例

什么是折半查找法

折半查找法（也称二分查找法）是一种常用的查找算法。它是根据定位元素与查找范围中间元素的比较结果，将查找范围逐渐缩小，最终定位到所查找的元素的过程。

其基本思路可以用以下伪代码表示：

// array是一个已经按照从小到大排序好的数组，n是数组长度，x是要查找的元素
binary_search(array, n, x) {
    left = 0, right = n - 1
    while (left <= right) {
        mid = (left + right) / 2
        if (array[mid] == x)
            return mid
        else if (array[mid] < x)
            left = mid + 1
        else
            right = mid - 1
    }
    return -1
}

折半查找法的时间复杂度

折半查找法的时间复杂度为$O(\log n)$，其中$n$表示查找范围中元素的个数。这意味着，随着查找范围的增大，折半查找法的效率将会迅速提高。

使用折半查找法的步骤

使用折半查找法的步骤大致如下：

1. 将要查找的元素与查找范围中间的元素比较。
2. 如果它们相等，则查找结束，返回该元素的位置。
3. 如果要查找的元素比中间的元素小，则在查找范围的左半部分继续查找。
4. 如果要查找的元素比中间的元素大，则在查找范围的右半部分继续查找。
5. 重复以上步骤，直到找到要查找的元素或查找范围为空。

折半查找法的示例

以下是两个使用折半查找法的示例。

示例 1：查找一个整数是否存在于已排序的整数数组中

假设我们有一个已经按照从小到大排序好的整数数组arr，长度为n。我们需要编写一个函数来判断给定的整数x是否在该数组中存在，如果存在，则返回它的位置，否则返回-1。

可以使用折半查找法来实现上述功能。代码如下：

int binary_search(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid] < x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

示例 2：查找一个字符串是否存在于已排序的字符串数组中

假设我们有一个已经按照从小到大排序好的字符串数组str_arr，长度为n。我们需要编写一个函数来判断给定的字符串str是否在该数组中存在，如果存在，则返回它的位置，否则返回-1。

可以使用折半查找法来实现上述功能。代码如下：

int binary_search(char *str_arr[], int n, char *str) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int cmp = strcmp(str_arr[mid], str);
        if (cmp == 0)
            return mid;
        else if (cmp < 0)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

注意，对于字符串数组的折半查找，我们需要使用strcmp函数来进行字符串的比较。