二分查找的通用模型与常见错误

在算法面试中，二分查找（Binary Search） 是一个非常重要的知识点。许多人在实际应用时会遇到边界处理的问题，导致程序出现 bug。本文将总结二分查找的通用模型，并分析常见错误。

1. 二分查找的基本思想

二分查找适用于 有序数组，其核心思想是不断缩小搜索范围，直到找到目标值或确定目标值不存在。

二分查找主要有三种常见形式：

  • 标准二分查找（查找具体值）
  • 搜索左边界（Lower Bound）
  • 搜索右边界（Upper Bound）

2. 标准二分查找（查找具体值）

左闭右闭区间 [left, right]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

左闭右开区间 [left, right)（推荐）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return -1
}

两种方式的对比

方式right 初始化终止条件right 更新方式left 更新方式
左闭右闭 [left, right]len(nums)-1left <= rightright = mid - 1left = mid + 1
左闭右开 [left, right)len(nums)left < rightright = midleft = mid + 1

推荐使用 左闭右开 [left, right) 的写法，因为它避免了 right = mid - 1 这种可能导致边界问题的操作。

3. 搜索左边界（Lower Bound）

目标：查找 target 在数组中的第一个出现位置，或第一个大于等于 target 的元素索引。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

常见错误：

  • right 应该初始化为 len(nums)，而不是 len(nums)-1。
  • right = mid 而不是 right = mid - 1，否则可能跳过正确答案。

4. 搜索右边界（Upper Bound）

目标：查找 target 的最后一个出现位置 + 1，或者第一个大于 target 的元素索引。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func upperBound(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

常见错误：

  • right 应该初始化为 len(nums)，否则可能会遗漏边界情况。
  • right = mid 而不是 right = mid - 1，防止跳过正确的 mid 位置。

5. 统一的二分查找模板

为了让代码更加统一，我们可以使用 左闭右开 [left, right) 的形式来实现所有二分查找。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func binarySearchTemplate(nums []int, target int, isLowerBound bool) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > target || (isLowerBound && nums[mid] == target) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}
  • 查找 target：binarySearchTemplate(nums, target, false)
  • 查找左边界：binarySearchTemplate(nums, target, true)
  • 查找右边界：binarySearchTemplate(nums, target+1, true)

6. 总结

查找方式适用场景终止条件if 逻辑
标准二分查找查找 target 是否存在left < rightnums[mid] == target
左边界（Lower Bound）找 target 的第一个位置left < rightnums[mid] >= target
右边界（Upper Bound）找 target 的最后一个位置+1left < rightnums[mid] > target

推荐：统一使用 [left, right) 方式，逻辑更清晰，错误率更低！

希望这篇文章能帮助你更好地理解二分查找！你在实际写二分查找时遇到哪些问题呢？欢迎留言交流！