关于二分查找时的边界分类问题

前言

众所周知，我们在优化有关查找的算法时，都会用到二分，但是不同的题用到的二分查找，其左右边界/中点的处理大多都不相同，所以在这里写一下关于一些常见二分边界的种类。

---

正文

注意，二分查找基于数组有序

查找左右边界

• 左边界

  查找左边界，也就是某个数字的起始位置，由于我们采取向下取整的方式，所以在更新变量l的时候，需要+1来避免陷入无限循环(比如l = 1, r = 2 此时进入到else分支的时候)

  然后最关键的就是边界怎么找？

  其实很简单，由于我们现在想要找到左边界，所以当我们查找的数字有多个的时候，肯定会出现这个情况：mid = target，此时我们只需要变更一下二分查找的右边界，直到mid != target，再变更左边界，这样一来，在循环的最后，l = x[n], r = x[x + 1], 此时 r = target，而l刚好是target前一个元素，这样不就找到了我们的左边界吗?

  	for l < r {
  		mid := (l + r) / 2
  		if x[mid] >= target {
  			r = mid
  		} else {
  			l = mid + 1
  		}
  	}

• 右边界

  此时不要以为将左边界里面的等号去掉就万事大吉了，事实上，这是错误的做法

  由于此时我们寻找的是右边界，所以等号去掉仅仅是第一步，我们可以来看一个例子：

  {1,2,3,4},target = 2，如果仅仅是将等号去掉，你猜猜这样得到的答案是什么？ans = 2，仔细分析我们就可以弄清楚，当我们得到了x[mid] == target的情况，倘若我们再对mid + 1，此时l这个边界很可能对应的就不再是target的值了，所以我们不能对l = mid + 1 操作。

  此时怎么办？既然l不能等于mid + 1， 那么r = mid - 1，总可以了吧，此时我们也要对mid的计算进行一些改变，之前我们直接对小数部分进行了舍弃，然而，在这里如果继续沿用舍去小数部分的做法，是会出错的，比如区间[1,2]，所以这里采取四舍五入的做法，能够正确的变更边界。

  	for l < r {
  		mid := (l + r + 1) / 2
  		if x[mid] > target {
  			r = mid - 1
  		} else {
  			l = mid
  		}
  	}

查找插入位置

• 插入位置(右边界)

  有时，我们还会碰到一些数组中可能不存在的target，然后我们需要找到正确的位置并插入，插入后能够保证原数组的有序性。

  正确的位置也就是数组中最后一个存储的数值是小于或等于target的位置的下一个位置，虽然采取直接查找第一个大于target的值这个策略也行，但是某些情况下并不适合使用这种策略。

  在遇到数组中有多个相同元素的时候，某种意义上我们也要寻找这个元素的左边界，但是我们有需要查找“最后一个”位置，某种意义上我们还需要找到“右边界”，所以我们要将以上两者相结合。

  由于在遇到相等的情况时，我们需要查找左边界，所以当x[mid] == target时，移动右边界。

  同时在x[mid] < target时，我们需要移动我们的左边界，基本思路定好了，剩下便是一些细节的+1还是-1还是不加不减的问题，所以此时，我们最好分析一些边界情况：

  [1,6]，插入的数值为6，此时，由于我们还没有选取mid应该采用的计算方式，所以我们先看if语句，倘若mid舍去小数，那么我们的r = mid, l = mid + 1，此时，找到的便是我们的位置1，是错误的，所以我们采取四舍五入的方法，此时， r = mid - 1, l = mid，找到下标0，结果正确。

  	for l < r {
  		mid := (l + r + 1) / 2
  		if x[mid] < target {
  			l = mid
  		} else {
  			r = mid - 1
  		}
  	}

• 插入位置(左边界)

  但是有的时候，第一种左边界插入的方法并不适合所有情景，比如[0,1]，插入-1的情况，如果我们通过第一种方法，也只能找到下标为0的数字，此时我们计算出来的插入位是下标为1的位置，是错误的，所以此时有第二种方法，右边界插入，此时，我们要寻找的是第一个大于target的位置，也就是左边界，在if语句取等时，左边界移动，如何判断±1的问题？

  同样的，我们可以来看边界情况[2,4],插入数字1，最后，我们的l应该为最终的插入位置，r则为l - 1，此时，l最终为0， r最终为-1，只有令r = mid - 1 才能实现，同时，为了达成负数的目标，并且需要精确找到位置，循环的结束条件使用l<=r，mid = (l + r) / 2，既然如此，为了避免陷入无限循环，l = mid + 1这一步也确定了，于是就可以完成我们的二分插入代码了。

          for l <= r {
              mid := (l + r) / 2
              if nums1[mid] > nums2[i] {
                  r = mid - 1
              } else {
                  l = mid + 1
              }
          }

---

这部分去想还是挺困难的，比较好的记忆办法就是自己在脑海里面想一遍，然后理解着敲出来。