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

什么是折半查找

折半查找（也称二分查找）是一种在有序数组中查找指定元素的查找算法，时间复杂度为O(logn)。

实现步骤

在实现折半查找前，需要明确以下几个步骤：

1. 确定查找区间范围；
2. 计算查找区间的中间位置；
3. 比较中间位置和目标值；
4. 不断缩小查找范围，直到找到目标值或者查找区间为空。

下面我们来一步步实现。

定义函数

首先需要定义一个 binary_search 函数，该函数接受三个参数：有序数组、数组元素个数和目标值，并返回目标值在数组中的索引。

int binary_search(int arr[], int len, int target) {
    // ...
}

确定查找区间范围

由于折半查找是在有序数组中查找，因此我们需要确定查找区间范围。初始时，查找范围为整个数组，即左右指针初始分别指向数组的第一个和最后一个元素。具体实现如下：

int left = 0;
int right = len - 1;

计算查找区间的中间位置

当确定了查找区间之后，我们需要计算中间位置，即 (left + right) / 2。注意，在计算中间位置时，可能会出现整数溢出的问题，因此最好使用下面的方式计算中间位置，避免整数溢出：

int mid = left + (right - left) / 2;

比较中间位置和目标值

我们用 mid 指向的元素的值与目标值进行比较。如果相等，则返回 mid，否则根据比较结果，更新查找区间。

if (arr[mid] == target) {
    return mid;
} else if (arr[mid] < target) {
    left = mid + 1;
} else {
    right = mid - 1;
}

如果中间元素小于目标值，说明目标值可能在右半边，因此更新左指针为 mid + 1；如果中间元素大于目标值，说明目标值可能在左半边，因此更新右指针为 mid - 1。

缩小查找范围

根据比较结果，我们更新查找区间，并重复上述步骤。具体实现如下：

while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

完整代码

综上所述， binary_search 函数的完整代码如下：

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

示例

下面是两个例子，演示了如何使用 binary_search 函数进行折半查找。

#include <stdio.h>

int binary_search(int arr[], int len, int target);

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int len = sizeof(arr) / sizeof(int);
    int target = 7;
    int index = binary_search(arr, len, target);
    if (index == -1) {
        printf("%d not exist in arr\n", target);
    } else {
        printf("%d at %d position of arr\n", target, index);
    }
    return 0;
}

输出：

7 at 3 position of arr

#include <stdio.h>

int binary_search(int arr[], int len, int target);

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int len = sizeof(arr) / sizeof(int);
    int target = 6;
    int index = binary_search(arr, len, target);
    if (index == -1) {
        printf("%d not exist in arr\n", target);
    } else {
        printf("%d at %d position of arr\n", target, index);
    }
    return 0;
}

输出：

6 not exist in arr

总结

折半查找是一种高效的查找算法，它的时间复杂度为O(logn)，可以快速查找有序数组或者链表中的元素。掌握折半查找的实现方法，对于提高编程能力和解决实际问题都是非常有帮助的。