理解折半查找法

理解折半查找法：高效的查找算法

折半查找法（又称二分查找法）是一种高效的查找算法，用于查找一个已排序数组中的目标元素。与线性查找方法不同，折半查找每次都将搜索范围减半，从而大幅提升查找效率。本文将详细分析折半查找的工作原理，并以查找目标值 13 为例进行内存分析。

折半查找法的基本原理

折半查找法基于这样一个假设：目标数据已经排好序。该算法通过不断地将查找范围一分为二，逐步缩小查找范围，从而在较短的时间内找到目标元素。具体步骤如下：

1. 初始化：设定一个查找范围，包括 left 和 right，分别代表数组的起始索引和结束索引。
2. 计算中间元素：每次计算中间元素的位置，mid = left + (right - left) / 2，并与目标值进行比较。
3. 缩小查找范围：
   • 如果目标值等于中间元素，返回该元素的索引。
   • 如果目标值小于中间元素，说明目标值在左半部分，将 right 设置为 mid - 1。
   • 如果目标值大于中间元素，说明目标值在右半部分，将 left 设置为 mid + 1。
4. 循环：重复上述步骤，直到找到目标元素或查找范围为空（left > right）。

折半查找法的时间复杂度

折半查找的时间复杂度是 (O(\log n))，其中 n 是数组的大小。每次比较都会将查找范围减半，因此不需要遍历整个数组。相比于线性查找的 (O(n))，折半查找法的效率要高得多，尤其是在数据量较大的情况下。

源代码实现

下面是实现折半查找的 C++ 代码：

#include <iostream>
using namespace std;

// 折半查找函数，返回目标值的索引，找不到返回 -1
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出

        // 检查中间元素是否是目标值
        if (arr[mid] == target) {
            return mid; // 找到目标，返回索引
        }
        // 如果目标值小于中间元素，缩小右边界
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        // 如果目标值大于中间元素，缩小左边界
        else {
            left = mid + 1;
        }
    }

    return -1; // 目标值不在数组中
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // 必须是有序数组
    int size = sizeof(arr) / sizeof(arr[0]);
    int target;

    cout << "Enter the number to search: ";
    cin >> target;

    int result = binarySearch(arr, size, target);

    if (result != -1) {
        cout << "Found " << target << " at index " << result << endl;
    } else {
        cout << target << " is not in the array." << endl;
    }

    return 0;
}

以查找目标值 13 为例

假设我们有一个有序数组 arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，并且我们的目标值是 13，我们将在数组中查找目标值。

初始设置：

• 数组 arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}。
• 目标值 target = 13。
• 数组大小 size = 10，即 arr 的长度。
• 初始值：left = 0，right = 9。

1. 第一次迭代：

• left = 0, right = 9。
• 计算中间索引 mid = 0 + (9 - 0) / 2 = 4，即 mid = 4。
• 访问 arr[mid]，即 arr[4] = 9。

比较 arr[mid] 与目标值 target：

• arr[mid] = 9，目标值 13 大于 9，因此目标值在右侧。

更新 left = mid + 1 = 4 + 1 = 5，新的查找区间是 [5, 9]。

2. 第二次迭代：

• left = 5, right = 9。
• 计算中间索引 mid = 5 + (9 - 5) / 2 = 7，即 mid = 7。
• 访问 arr[mid]，即 arr[7] = 15。

比较 arr[mid] 与目标值 target：

• arr[mid] = 15，目标值 13 小于 15，因此目标值在左侧。

更新 right = mid - 1 = 7 - 1 = 6，新的查找区间是 [5, 6]。

3. 第三次迭代：

• left = 5, right = 6。
• 计算中间索引 mid = 5 + (6 - 5) / 2 = 5，即 mid = 5。
• 访问 arr[mid]，即 arr[5] = 11。

比较 arr[mid] 与目标值 target：

• arr[mid] = 11，目标值 13 大于 11，因此目标值在右侧。

更新 left = mid + 1 = 5 + 1 = 6，新的查找区间是 [6, 6]。

4. 第四次迭代：

• left = 6, right = 6。
• 计算中间索引 mid = 6 + (6 - 6) / 2 = 6，即 mid = 6。
• 访问 arr[mid]，即 arr[6] = 13。

比较 arr[mid] 与目标值 target：

• arr[mid] = 13，目标值 13 相等，查找成功。

返回索引 6，即目标值 13 的位置。

内存分析

每次迭代，程序都会读取 arr[mid] 并进行比较。内存访问是按需进行的，程序仅读取当前中间位置的值，而不是遍历整个数组。每次查找范围缩小后，left 和 right 指针更新，从而减少了对内存的访问。通过每次将查找范围缩小一半，折半查找能够快速找到目标值，避免了不必要的内存读取。

总结

折半查找法通过每次将查找范围缩小一半，显著提高了查找效率。在有序数组中，我们能够在 (O(\log n)) 的时间复杂度内查找到目标元素。每次对数组元素的访问都是必要的，避免了线性查找中的不必要访问，使得内存访问更加高效。对于大规模数据集，折半查找法是一种理想的查找方法。