myEsn2E9

[二分查找 binary search] 是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮减少一半搜索范围，直至找到目标元素或搜索区间为空为止。

先初始化指针 i=0 和 j=n-1，分别指向数组首元素和尾元素，代表搜索区间 [0, n-1]。中括号表示闭区间 ，其包含边界值本身。

接下来，循环执行以下两步：

1. 计算中点索引 $m = \lfloor {(i + j) / 2} \rfloor$，其中 $\lfloor : \rfloor$ 表示向下取整操作。
2. 判断 nums[m] 和 target 的大小关系，分为以下三种情况：
   1. 当 nums[m] < target ，说明 target 在区间 [m+1, j] 中，因此执行 i=m+1。
   2. 当 nums[m] > target ，说明 target 在区间 [i, m-1] 中，因此执行 j=m-1。
   3. 当 nums[m] = target ，说明找到 target ，因此返回索引 m。

若数组不包含目标元素，搜索区间最终会缩小为空。此时返回 -1。

值得注意的是，由于 i 和 j 都是 int 类型，因此 i+j 可能会超出 类型的取值范围。为了避免大数越界，通常采用公式 $m = \lfloor {i + (j - i) / 2} \rfloor$ 来计算中点。

/* 二分查找（双闭区间） */
int BinarySearch(int[] nums, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = nums.Length - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        int m = i + (j - i) / 2;   // 计算中点索引 m
        if (nums[m] < target)      // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else                       // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

优点：时间和空间方面都有较好的性能。

局限性：

• 仅适用有序数据，若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。
• 仅适用于数组（连续存储空间）。
• 小数据量下，线性查找性能更佳，在算法题中，常通过将线性查找替换为哈希查找来降低算法的时间复杂度。
  • 线性查找：以时间换空间
  • 哈希查找：以空间换时间

二分查找插入点：二分查找不仅可用于搜索目标元素，还具有许多变种问题，比如搜索目标元素的插入位置。

二分查找边界：

1. 查找左边界
2. 查找右边界

线性搜索适用于小型或频繁更新的数据；

二分查找适用于大型、排序的数据；

哈希查找适合对查询效率要求较高且无须范围查询的数据；

树查找适用于需要维护顺序和支持范围查询的大型动态数据。

参考#

• 第 10 章   搜索 - Hello 算法 (hello-algo.com)