• 二分查找的核心思想是：逐渐缩小问题规模
  • 首先着眼掌握算法的思想，而不该去纠结二分的几种写法区别和细节，这样会使自己更乱
  • 面对问题，如何分析，利用单调性（绝大多数二分查找问题利用的是单调性）或者题目本身蕴含的可以逐渐缩小问题规模的特性解决问题，而不是纠结二分查找怎么写。

最基本问题

二分查找的基本问题是「力扣」第 704 题：二分查找。

  1. func search(nums []int, target int) int {
  2.     left, right := 0, len(nums)-1
  3.     // [left, right]
  4.     for left <= right {
  5.         mid := left + (right-left)>>1
  6.         if nums[mid] == target {
  7.             return mid
  8.         } else if nums[mid] > target {
  9.             // [left, mid-1]
  10.             right = mid - 1
  11.         } else {
  12.             // [mid+1, left]
  13.             left = mid + 1
  14.         }
  15.     }
  16.     return -1
  17. }

基本思想是：根据待搜索区间的中间元素 nums[mid] 与 target 大小关系，来判断下一轮搜索在哪个区间查找，进而设置 left 和 right 的值。

  • nums[mid] == target 找到目标元素，返回 mid
  • nums[mid] > target 说明 mid 及其右边的元素一定都比 target 大 ，下一轮搜索需要在区间 [left, mid -1] 里查找，所以这时候需要设置 right = mid -1
  • nums[mid] < target 说明 mid 及其左边的元素一定都比 target 小 ，下一轮搜索需要在区间 [mid +1, right] 里查找，所以这时候需要设置 left = mid + 1

当退出循环时，表示区间内不存在目标元素，返回 -1

二分查找的变种问题

  • 大于等于 target 的下标最小的元素
  • 小于等于 target 的下标最大的元素

这类问题的特点是：当看到 nums[mid] == target 时，我们仍需要继续查找，继续看看左边元素的值或右边元素的值。

将待搜索区域分成两部分（重点）

根据看到的中间位置的 nums[mid] 将待搜索区分为两个部分：

  • 一定不存在 目标元素的区域：下一轮搜索不用考虑它
  • 可能存在 目标元素的区域：下一轮搜索需要考虑它

这种时候 mid 只有可能被分到这两个区间中的一个，即 if...else... 中的一个：

  • 如果 mid 被分到左边区域（左边是可能存在目标元素的区域），那么区间分成了 [left, mid] 和 [mid + 1, right] ，所以设置就是 right = mid , left = mid + 1
  • 如果 mid 被分到右边区域（右边是可能存在目标元素的区域），那么区间分成了 [left, mid -1] 和 [mid, right] ，所以设置就是 right = mid - 1 , left = mid

这时候 循环的条件应该是 for left < right ，在上面把待搜索区间分成两个部分的情况下，循环退出一定有 left == right 成立，所以这时候循环退出时不需要考虑返回 left 还是 right
image.png

重要经验：

在写 if 语句时，把容易想到的，不容易出错的逻辑写在 if 条件语句里，这样就把复杂的、容易出错的逻辑放在 else 部分中，这样编写代码就不容易出错了。

那么怎么定义容易想到，不容易出错的呢？举个栗子，题目要求我们找符合条件 a 的元素，那么我们就对条件 a 取反面，这样分析就不容易出错。
举个栗子：题目要求我们找到第一个大于等于 target 的元素下标，那么小于 target 的元素一定不是我们要找的。

  1. if nums[mid] < target {
  2.     // [mid + 1, right]
  3.      left = mid + 1   
  4. }

剩下的情况放在 else 中，有些时候我们甚至不用分析 else 是什么情况。因为 if 的区间是 [mid + 1, right] ，所以他的反面就是 [left, mid] ，这时候 else 的设置就是 right = mid 。
所以完整逻辑是

  1. if nums[mid] < target {
  2.     left = mid + 1
  3. } else {
  4.     right = mid 
  5. }

上述，总结起来就是一句话：我们 总是在区间 **[left, right]** 里查找目标元素。

注意：我们说的是 左闭右闭区间，为什么不是 左闭右开 区间呢？如果是 左闭右开，我们需要 把部分精力放在考虑右边界是不是可以取到这件事情上，因为任意一个左闭右开区间 [left, right) 一定唯一对应一个 左闭右闭区间 [left, right -1] 。所以到底是开区间还是闭区间，前后保持一致就好了。
注意：永远要思考下一轮搜索应该在哪个区间，就能考虑清楚到底下一轮更新的是 left 还是 right，到底加不加 1 ， 减不减 1 。

例题：35 题：搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:

  1. 输入: [1,3,5,6], 5
  2. 输出: 2

示例 2:

  1. 输入: [1,3,5,6], 2
  2. 输出: 1

示例 3:

  1. 输入: [1,3,5,6], 7
  2. 输出: 4

示例 4:

  1. 输入: [1,3,5,6], 0
  2. 输出: 0

这里可以把题意理解为，寻找第一个大于等于目标元素的下标。
那么如果 nums[mid] < target，那么 [left, mid] 一定不是我们要找的，所以相应的区间就是 [mid +1, right] ，也就是这时候需要设置 left = mid + 1 

  1. func searchInsert(nums []int, target int) int {
  2.     n := len(nums)
  3.     lo, hi := 0, n-1
  4.     for lo < hi {
  5.         mid := lo + (hi-lo)>>1
  6.         if nums[mid] < target {
  7.             // [mid+1, right]
  8.             lo = mid + 1
  9.         } else {
  10.             // [left, mid]
  11.             hi = mid
  12.         }
  13.     }
  14.     return lo
  15. }

注： left < righ 的退出条件是 left = right ，闭区间 [left, right] 所以 left 值没有被计算哦。实际上是因为这道题题意中 [left, right] 中一定存在插入元素的位置。

例题2：704 题：二分查找

就是标准的二分查找

  1. func search(nums []int, target int) int {
  2.     left, right := 0, len(nums)-1
  3.     for left < right {
  4.         mid := left + (right-left)>>1
  5.         if nums[mid] < target {
  6.             // [mid + 1, right]
  7.             left = mid + 1
  8.         } else {
  9.             // [left, mid]
  10.             right = mid
  11.         }
  12.     }
  13.     if nums[left] == target {
  14.         return left
  15.     }
  16.     return -1
  17. }

注：这里我们还不能判断 nums[left] 是否等于 target ，所以还需要单独判断一次。

区别

这里比较的是 for left <= right 和 for left < right 的区别

for left <= right

这种写法可以认为在循环体内部直接查找元素，把搜索区间分成三个部分。
选择 nums[mid] 的值看一下。image.png
如果中间位置的元素的值等于目标元素就直接返回。如果中间位置的元素不是目标元素，可以根据中间位置元素的值决定在中间位置的左边还是右边继续查找。这种查找方式把待搜索区间分为三个部分：左、中、右。
image.png
重要经验：当我们要找的元素非常明确、并且简单，通常可以这么写。

for left < right

这种写法表示在循环体内部排除元素，把当前搜索区分成两个部分。
可以理解为两边夹，在解决复杂问题时，会使得思考的过程变得简单。

选择 nums[mid] 的值看一下。
image.png
分析：在什么情况下，目标元素在哪个区间里，把区间分为 一定不存在目标元素的区间 和 可能存在目标元素的区间。而 mid 只可能位于这两个区间中的一个，所以可以分为下面四种情况。
image.png
总结起来，就两种情况，mid 左边区间时 和 mid 在右边区间。

重要经验：
如果我们要找的元素的性质比较复杂：例如需要满足「条件 1」并且「条件 2」。我们在编写 if 语句的时候，就可以把其中一个条件取反，就可以达到缩减搜索区间的目的。

这一点也不难想明白，「条件 1」并且「条件 2」的反面就是「取反条件 1」或者「取反条件 2」。再举一个具体的例子：例如我们要找一个数 x，需要满足 4≤x≤9，即 4x≥4 并且 x≤9。如果我们看到一个数小于 4，我们就知道此时需要在当前位置的右边继续查找，可以得到缩减问题区间的目的。

细节

有些时候 mid 要向上取整

跟区间划分有关，如果不调整，会出现死循环。

image.png
举个栗子，现在的搜索的数组是 [2,3] 他们的 index 分别是 0, 1，这时候 left = 0, right = 1 ，如果我们要找的 target是 2，mid 向下取整，那么这时候 nums[mid] > target 成立，那么这时候搜索区间就变成了 [left, mid -1] 和 [mid, right]