二分查找的关键

2020年4月20日 下午10:24

关键点：

1. 定义：我们要找的值在[left,right]闭区间中。在循环的过程中我们要维护这个定义，知道left = right，就可以找到我们target
   1. 注意：这里的[left,right]区间要包括所有的情况，有些题目初始化right = nums.size() 而不是nums.size() - 1就是这个原因
2. 在循环的过程中需要维护两个条件：
   1. 在[left,right]闭区间的包含target的定义
   2. 并且，每次循环保证[left,right]区间在缩小，否则会造成死循环
      1. 这里就需要考虑上取整 or 下取整
         1. 上取整 mid = right + (left - right) / 2
         2. 下取整 mid = right + (left - right - 1) / 2
            1. mid = (left + right) / 2
      2. 经验结论：
         1. left = mid or right = mid - 1 => 上取整
         2. left = mid + 1 or right = mid => 下取整

例题：

LCP 08. 剧情触发时间
35. 搜索插入位置