二分查找（折半查找）

作者：马育民 • • 阅读：10294

废弃废弃

详见：https://www.malaoshi.top/show_1GWvY9LAMNU.html

介绍

二分查找（也叫折半查找），这是一种高效的查找算法，只能 用于 有序的线性集合，通过不断缩小查找范围实现快速查找，比逐个遍历的顺序查找效率高得多。

前提

必须 先排序，如果是乱序的，那么就没法用 二分查找算法了。

查找思想

二分查找通过比较数组 中间的数据 与 目标数据 的大小，可以得知目标数据是在 数组的左边还是右边。因此，比较一次就可以把 查找范围缩小一半。重复执行该操作就可以找到目标数据，或得出目标数据不存在的结论。

步骤

  1. 排序：先对数组进行排序：升序或降序，因为折半查找依赖于数据的有序性

  2. 初始化：确定数组的起始点 start（通常为索引0）和结束点 end（数组长度减1）

  3. 查找过程：

    1. 计算中间位置 mid，公式一般为 mid = (start + end) // 2 （使用整除以确保mid为整数）。

    2. 比较 目标值 与中间位置的值：

      • 如果目标值等于中间位置的值，则查找成功，返回该位置。

      • 如果目标值小于中间位置的值，在数组的左半部分继续查找，即：更新结束位置为 end = mid - 1

      • 如果目标值大于中间位置的值，在数组的右半部分继续查找，即：更新起始位置为 start = mid + 1

  4. 重复 步骤3，直到找到目标，或左边界 > 右边界（说明集合中无目标值）。

例子

假设待查找数列为 1、3、5、7、9、11、19，我们要找的元素为 19，下面进行二分查找。

首先待查数列如下图，找到中间的元素 7（ 索引：(0+6)/2=3，即：第 4 个位置上的元素）

中间元素为 7，要找的元素 19 比 7 大，于是在后半部分查找，现在后半部分数列为 9、11、19，找到中间元素，如下图：

中间元素为 11，要找的元素 19 比 11 大，则继续在后半部分查找，后半部分只有一个元素 19 了，这时直接与 19 比较，相等，结束查找。

查找次数

最好情况

1次比较 ，目标在中间位置

最坏情况

总共有 n 个元素，要查找的元素在最后，操作如下：

  1. 初始时，数组长度为 n

  2. 第1次比较后，搜索范围缩小一半，因此剩下的元素数量 \frac{n}{2}

  3. 第2次比较后，剩下的元素数量 \frac{n}{4}

  4. 第k次比较后，剩下的元素数量 \frac{n}{2^k}

当剩下的元素数量为 1 时，表示找到了，所以：

\frac{n}{2^k}=1

可得 k = \log_2n,（是以 2 为底，n 的对数）

最多查找次数：\log_2n

例子

长度是16的数组，要查找的元素在最后一位，需要查找 5 次，即：log_216 = 4

时间复杂度

根据查找次数可知：O(\log_2n)

空间复杂度

迭代版 O(1)

优缺点

每次查找都会将范围缩小一半，时间复杂度为 $O(log_2n)$（n为集合元素个数），比如n=1000时，最多只需10次查找，而顺序查找最多需要1000次。

实现

迭代版（工业常用），逻辑清晰、效率高，无递归的栈开销，是实际开发中最常用的写法，

java

public class BinarySearch {
    /**
     * 二分查找迭代版（适用于 升序排列 的int数组）
     * @param sortedArr 升序有序的目标数组
     * @param target    要查找的目标值
     * @return 找到则返回对应索引，未找到/数组无效返回-1
     */
    public static int binarySearch(int[] sortedArr, int target) {
        // 健壮性处理：数组为null或空数组，直接返回-1
        if (sortedArr == null || sortedArr.length == 0) {
            return -1;
        }

        int left = 0; // 查找范围左边界（初始为数组首索引）
        int right = sortedArr.length - 1; // 查找范围右边界（初始为数组尾索引）

        // 循环条件：left <= right 【核心！避免漏查最后一个元素】
        while (left <= right) {
            // 计算中间索引：left + (right - left) / 2 【避免left+right整数溢出，比(left+right)/2更安全】
            int mid = left + (right - left) / 2;

            if (sortedArr[mid] == target) {
                return mid; // 找到目标，直接返回中间索引
            } else if (sortedArr[mid] > target) {
                // 目标在左半区，缩小右边界（mid已比较过，无需再查）
                right = mid - 1;
            } else {
                // 目标在右半区，缩小左边界（mid已比较过，无需再查）
                left = mid + 1;
            }
        }
        // 循环结束仍未找到，返回-1
        return -1;
    }

    // 测试用例
    public static void main(String[] args) {
        // 测试1：常规升序数组，查找存在的元素
        int[] arr1 = {1, 3, 5, 7, 9, 11, 13, 15};
        int target1 = 7;
        System.out.println("目标" + target1 + "的索引：" + binarySearch(arr1, target1)); // 输出：3

        // 测试2：查找不存在的元素
        int target2 = 4;
        System.out.println("目标" + target2 + "的索引：" + binarySearch(arr1, target2)); // 输出：-1

        // 测试3：查找数组首元素
        int target3 = 1;
        System.out.println("目标" + target3 + "的索引：" + binarySearch(arr1, target3)); // 输出：0

        // 测试4：查找数组尾元素
        int target4 = 15;
        System.out.println("目标" + target4 + "的索引：" + binarySearch(arr1, target4)); // 输出：7

        // 测试5：空数组/空指针
        int[] arr2 = {};
        int[] arr3 = null;
        System.out.println("空数组查找结果：" + binarySearch(arr2, 5)); // 输出：-1
        System.out.println("空指针查找结果：" + binarySearch(arr3, 5)); // 输出：-1

        // 测试6：单元素数组
        int[] arr4 = {6};
        System.out.println("单元素存在：" + binarySearch(arr4, 6)); // 输出：0
        System.out.println("单元素不存在：" + binarySearch(arr4, 8)); // 输出：-1
    }
}

python

def binary_search(arr, target):
    left = 0  # 左边界
    right = len(arr) - 1  # 右边界

    while left <= right:  # 注意：条件是<=，否则会漏掉最后一个元素
        mid = (left + right) // 2  # 中间位置（避免溢出也可写：left + (right - left) // 2）
        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] > target:
            right = mid - 1  # 目标在左半区，缩小右边界
        else:
            left = mid + 1  # 目标在右半区，缩小左边界
    return -1  # 未找到目标，返回-1

# 测试
if __name__ == "__main__":
    sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15]
    target1 = 7
    target2 = 4
    print(f"目标{target1}的索引：{binary_search(sorted_arr, target1)}")  # 输出：3
    print(f"目标{target2}的索引：{binary_search(sorted_arr, target2)}")  # 输出：-1

原文出处：/show_1IX3MMgVzX5P.html

吉ICP备15003043号