不需要关心左开右闭还是左闭右开。
始终认为是 [left, right] 即可。

每次做的核心就是明确下一步搜索区间。

举个栗子 35 题，搜索元素的插入位置。
也就是左边界，第一个大于等于该值的位置，如果不存在就返回数组长度，表示应该插入到最后。

错误案例：

  1. function searchInsert(nums: number[], target: number): number {
  2.   let n = nums.length
  3.   if (nums[n-1] < target) {
  4.     return n
  5.   }
  6.   let l = 0
  7.   let r = n - 1
  9.   // [l, r]
  10.   while(l < r) {
  11.     let m = l  + (r - l >> 1)
  12.     console.log(l, r, m)
  13.     if (nums[m] > target) {
  14.       // 下一个区间 [l, m - 1]
  15.       r = m - 1
  16.     } else {
  17.       // 下一个区间 [m, r]
  18.       l = m
  19.     }
  20.   }
  21.   return l
  22. };

为什么说是错误案例呢？
举个例子 [1,3,5,6]

  1. l    r m
  2. -----
  3. 0    3    1
  4. 1 3 2
  5. 2 3 2
  6. 2    3 2
  7. ...

那么我们再来分析下为什么会有这种无限循环呢？

这里需要获得的是第一个大于等于 target 的位置。

我们这里使用的是 nums[m] > target

  • 满足，下一个搜索区间即 [l, m -1]
  • 不满足，下一个搜索区间即 [m, r]，由于 m = l + (r - l >> 1)，那么 存在 r = l - 1 始终能得到 m === l，这时候就会出现无限循环的场景。

正确案例

  1. function searchInsert(nums: number[], target: number): number {
  2.   let n = nums.length
  3.   if (nums[n-1] < target) {
  4.     return n
  5.   }
  6.   let l = 0
  7.   let r = n - 1
  9.   // [l, r]
  10.   while(l < r) {
  11.     let m = l  + (r - l >> 1)
  12.     // 由于是获取大于等于，所以先判断小于
  13.     if (nums[m] < target) {
  14.       // 下一个区间 [m + 1, r]
  15.       l = m + 1
  16.     } else {
  17.       // 下一个区间 [l, m]
  18.       r = m
  19.     }
  20.   }
  21.   return l
  22. };

怎么理解 while(l < r) 是左闭右闭区间？

其实不能这么说
while(l < r) 既不能说是左闭右开，也不能说是左闭右闭的区间。
实际上搜索的区间是看其边界的设置。
如果下一轮的搜索区间是 [l, mid] 我们这时候设置 r = mid + 1 ，那实际上就相当于 [l, r)左闭右开，如果我们设置 r = mid，那就是相当于是 [l,r] 左闭右闭。

所以对我们而言，不必过分不安息 左闭右开还是左闭右闭
这里的关键是 ：通过题意，得到某种单调性，和可以逐步缩小搜索规模的条件，进而准确地设计可以使得搜索区间缩小的条件。

二分法一定要要求当前数组有序嘛？

不必要。
例如力扣 33 题 搜索旋转排序数组。
我们是根据单调性来缩小区间。

为什么有时候 计算 mid 的时候需要 +1 ?

需要注意这种写法只会出现在 while(left < right)的时候，因为只有这种情况我们需要考虑，mid 位置的值是需要保留还是剔除，实际上就是上面的那俩栗子

  • 剔除：。当判断条件是 nums[mid] > target时 right = mid -1 否则是 left = mid；
  • 保留：当判断条件是 nums[mid] < target 时， left = mid + 1，否则是 right = mid

需要注意这时候会出现 left = mid 的情况，那么由于 mid = left + ( right - left >> 1) 当区间有偶数个数时，mid 只能取到中间偏左的那个数。
那么当 区间个数为 2 时，mid 只能取到 left ，从而变成了死循环，所以有时候需要 +1 ，保证取得是中间偏右的那个数。

就是为了避免死循环。

什么时候用 right = len，什么时候用 right= len-1?

具体根据问题描述
如力扣 35 题，查找插入位置，已知插入的元素有可能大于最后一个元素，所以这时候的插入位置是 len 。

什么时候向左边找，什么时候向右边找？

输入数组是升序，决定了向左边找，也就是说 nums[mid] < target 优先判断，这时候的组合是 left = mid + 1 和 right = mid
当输入数组是降序是，决定了向右边找，也就是说 nums[mid] > target优先判断，这时候的组合是 right = mid - 1 和 left = mid，需要注意这时候要使用 mid = left + (right - left + 1) >> 1

写法

  • while(left <= right) 这种写法中的 left 和 right 始终保持 加一或减一的 逻辑，需要注意的是：需要判断 mid 位置是否是解，把 mid 保存下来，所以这种写法也被称为是 带 ans的写法。
  • while(left < right) 一定要小心确定 mid 位置的去留情况 left = mid 和 right = mid -1 成对出现（这时候应该使用 mid = left + (right - left + 1 >> 1)， left = mid +1 和 right = mid 成对出现。这种写法的好处是退出循环的时候，始终有 left === right，且 该值很多时候就是需要的解。

image.png

总结

  • while(left < right) ，退出循环的时候 left === right成立，好处是不用判断应该返回 left 还是 right
  • 区间是 [left...right] 只有可能是下面两种划分区间
    • [left ...mid] [mid+1...right] 对应了 right = mid 和 left = mid + 1
    • [left ... mid-1] [mid...right] 对应了 left = mid 和 right = mid-1，这种情况下的 mid = left + (right - left + 1 >> 1) 避免死循环
  • 退出循环 left === right，如果确定 [left...right] 中一定有解，那么就直接返回 left 即可，否则还需要对 left 的值进行一次判断
  • 始终保持不变的是：在 区间 [left…right] 中查找目标元素

推荐 阅读 https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/xsq0b7/

https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/