labuladong_二分查找

零、二分查找框架

func binarySearch(nums []int, target int)int {
    left := 0, right := ...

    for ...  {
        mid := left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if nums[mid] < target {
            left = ...
        } else if nums[mid] > target {
            right = ...
        }
    }
    return ...
}

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。本文都会使用 else if，旨在讲清楚，读者理解后可自行简化。

其中 ... 标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。

另外声明一下，计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。