二分搜索

关注点

明确搜索的区间是左闭右闭区间[left, right]，还是左闭右开区间[left, right)。

强烈推荐

在分析搜索区间时，将搜索区间尽量转变成左闭右闭区间[left, right]，这种形式是最直观的。

根据中间位置元素的值nums[mid]可以把待搜索区间分为两个部分：

如何确定 left 和 right

明确循环可执行的条件是while(left < right)还是while(left <= right)，当上一步确定的搜索区间为空时，循环则终止。

形式	结论与建议
`while (left <= right)`	简单问题用，在循环体里能找到答案以后退出。
`while (left < right)`	复杂问题用，把答案留到退出循环以后，再判断。是解决二分问题的利器，尤其在边界问题用，这种方式考虑细节最少，但是需要一定练习才能灵活运用。
`while (left + 1 < right)`	不建议，本质上和 while (left <= right) 写法一样，盲目套这个所谓的最无脑模板，反而学不会二分。

while(left <= right)在退出循环的时候left = right + 1，即right在左，left在右。这种写法用在简单的二分问题中，如果题目要我们找的数的性质很简单，可以用这种写法，在循环体里找到了就退出。

while(left < right)写法的好处在于退出循环的时候left === right，把要找的数留到最后，在退出循环以后做判断。这种写法在思考复杂问题时，确实可以少考虑很多细节，把思考的精力用于求解问题上。但是尤其要注意死循环的情况。

只把区间分成两个部分，当循环判断条件为while(left < right)时，循环终止条件一定是left === right，此时返回left或right都行。

需要根据left/right新的取值情况来判断是使用上取整还是下取整，原则是不进入死循环。

比如，当if或else里有left = mid的时候，假设当区间里只剩下两个元素的时候，若mid下取整即mid还是left，且mid被划分到右边区间即会执行left = mid，导致left一直不变，进而进入死循环。针对这种情况，需要将mid调整为上取整。