【二分查找】二分查找总结

1、梳理二分查找：
（1）while (left < right) 退出循环的时候有 left == right 成立，因此无需考虑返回 left 还是 right；

（2）始终思考下一轮搜索区间是什么，如果是 [mid, right] 就对应 left = mid ，如果是 [left, mid - 1] 就对应 right = mid - 1，是保留 mid 还是 +1+1、-1−1 就在这样的思考中完成；

（3）从一个元素什么时候不是解开始考虑下一轮搜索区间是什么 ，把区间分为 2 个部分（一个部分肯定不存在目标元素，另一个部分有可能存在目标元素），问题会变得简单很多，这是一条 非常有用 的经验；

（4）在调试的过程中理解 区间和中间数划分的配对关系：
划分 [left, mid] 与 [mid + 1, right] ，mid 被分到左边，对应 int mid = left + (right - left) / 2;；
划分 [left, mid - 1] 与 [mid, right] ，mid 被分到右边，对应 int mid = left + (right - left + 1) / 2;。

2、二分查找的两种思路

思路 1：在循环体内部查找元素
while(left <= right) 这种写法表示在循环体内部直接查找元素；退出循环的时候 left 和 right 不重合，区间 [left, right] 是空区间。

思路 2：在循环体内部排除元素（重点）
while(left < right) 这种写法表示在循环体内部排除元素；
退出循环的时候 left 和 right 重合，区间 [left, right] 只剩下成 1 个元素，这个元素有可能就是我们要找的元素。

第 2 种思路可以归纳为「左右边界向中间走，两边夹」，这种思路在解决复杂问题的时候，可以使得思考的过程变得简单。

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