1.二分查找

约 1408 字大约 5 分钟...

二分查找

定义：

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

具体操作：

先初始化指针 $i = 0$ 和 $j = n - 1$ ，分别指向数组首元素和尾元素，代表搜索区间 $[0, n - 1]$
计算中点索引 $m = \lfloor {(i + j) / 2} \rfloor$ （其中 $\lfloor \: \rfloor$ 表示向下取整操作）
判断 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$ 。
重复2、3步骤，一直未找到元素，则搜索区间缩小为空。此时返回 $-1$ 。
注意项：由于 $i$ 和 $j$ 都是 int 类型，因此 $i + j$ 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 $m = \lfloor {i + (j - i) / 2} \rfloor$ 来计算中点

复杂度：

时间复杂度为 $O(\log n)$ ：在二分循环中，区间每轮缩小一半，因此循环次数为 $\log_2 n$ 。
空间复杂度为 $O(1)$ ：指针 $i$ 和 $j$ 使用常数大小空间。

区间表示法：

"双闭区间": 定义为 $[0, n]$
"左闭右开区间": 定义为 $[0, n)$

优缺点：

优点：
- 时间效率高，空间效率高
缺点：
- 仅适用于有序数据
- 仅适用于数组，因为需要随机跳跃，链表只能用指针遍历
- 小数据量时，不如线性搜索（因为线性搜索只需要1次比较操作）

代码实现：

/* 二分查找（双闭区间） */
func binarySearch(nums []int, target int) int {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    i, j := 0, len(nums)-1
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    for i <= j {
        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
}

二分查找变种问题：

二分查找不仅可用于搜索目标元素，还可用于解决目标元素的插入位置问题，

二分法查找插入点：

问题：

给定一个长度为n的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target，则插入到其左方。请返回插入后 target 在数组中的索引。

Case1：无重复元素的数组：

基于二分查找的思路，逼近最终查找值
- 当数组包含target时，插入点的索引就是该 target 的索引
- 当数组不包含 target 时， $i$ 即插入点位置。(越界时， $i$ 指向首个大于target的元素, $j$ 指向首个小于target的元素)

代码实现：

/* 二分查找插入点（无重复元素） */
func binarySearchInsertionSimple(nums []int, target int) int {
    // 初始化双闭区间 [0, n-1]
    i, j := 0, len(nums)-1
    for i <= j {
        // 计算中点索引 m
        m := i + (j-i)/2
        if nums[m] < target {
            // target 在区间 [m+1, j] 中
            i = m + 1
        } else if nums[m] > target {
            // target 在区间 [i, m-1] 中
            j = m - 1
        } else {
            // 找到 target ，返回插入点 m
            return m
        }
    }
    // 未找到 target ，返回插入点 i
    return i
}

Case2：有重复元素的数组：

问题改动点：数组存在重复元素
基于二分查找的思路，逼近最终查找值
- 当数组包含多个target 时
  - 方案1：使用线性搜索找到最左边的索引
  - 方案2：采用来j=m-1缩小区间，从而使指针j向小于target的元素靠近。
- 数组不包含target时：
  - $i$ 即插入点位置,(越界时，$i$指向首个大于target的元素,$j$指向首个小于target的元素)

代码实现：

    /* 二分查找插入点（存在重复元素） */
    func binarySearchInsertion(nums []int, target int) int {
        // 初始化双闭区间 [0, n-1]
        i, j := 0, len(nums)-1
        for i <= j {
            // 计算中点索引 m
            m := i + (j-i)/2
            if nums[m] < target {
                // target 在区间 [m+1, j] 中
                i = m + 1
            } else if nums[m] > target {
                // target 在区间 [i, m-1] 中
                j = m - 1
            } else {
                // 首个小于 target 的元素在区间 [i, m-1] 中
                j = m - 1
            }
        }
        // 返回插入点 i
        return i
    }

二分法查找边界：

问题：

给定一个长度为n的有序数组 nums ，其中可能包含重复元素。请返回数组中最左一个元素 target 的索引(左边界)。若数组中不包含该元素，则返回 -1。

思路：
- 找左边界，移动j，使得i无限逼近小于target的位置
- 找右边界，移动i，使得j无限逼近大于target的位置

代码实现：

/* 二分查找最左一个 target */
func binarySearchLeftEdge(nums []int, target int) int {
    // 等价于查找 target 的插入点
    i := binarySearchInsertion(nums, target)
    // 未找到 target ，返回 -1
    if i == len(nums) || nums[i] != target {
        return -1
    }
    // 找到 target ，返回索引 i
    return i
}