Algorithm-BinarySearch

关于 二分查找

• 最重要的就是分类讨论好二分，二分看着好写边界 case 还是需要测试的哈

• 什么是区间不变量？ 比如 区间取左闭右闭的话 那么每次区间二分 范围都是新区间的左闭右闭 后面做判断时 要一直基于这个左闭右闭的区间

• 其实区间定义成开或者闭都没有什么关系 只是要明确每次收缩范围后 范围内的元素是哪些 注意会不会漏掉边界就好

• 大家需要注意二分的几种情况
• 当l = 0, r = n的时候因为r这个值我们在数组中无法取到,while(l < r) 是正确写法
• 当l = 0, r = n - 1的时候因为r这个值我们在数组中可以取到,while(l <= r) 是正确写法 主要看能不能取到这个值

• 二分法有多种写法，末尾是开区间闭区间都可以解出寻找单个元素和寻找边界的题目，只需要注意相应的是l < r还是l <= r,每次取 mid 还是取 mid 加减一即可。建议理解后背熟一套模板，不要搞混。

• 其实二分还有很多应用场景，有着许多变体，比如说查找第一个大于 target 的元素或者第一个满足条件的元素，都是一样的，根据是否满足题目的条件来缩小答案所在的区间，这个就是二分的本质。另外需要注意，二分的使用前提：有序数组

• 二分的最大优势是在于其时间复杂度是O(logn)，因此看到有序数组都要第一时间反问自己是否可以使用二分。

• 关于二分 mid 溢出问题解答：
• mid = (l + r) / 2时，如果 l + r 大于 INT_MAX (C++内，就是int整型的上限)，那么就会产生溢出问题（int类型无法表示该数）
• 所以写成 mid = l + (r - l) / 2 或者 mid = l + ((r - l) >> 1) 可以避免溢出问题

• 对于二进制的正数来说，右移 x 位相当于除以 2 的 x 几次方，所以右移一位等于➗2，用位运算的好处是比直接相除的操作快

704 二分查找

1. 首先需要检测输入

2. 定义左右边界范围，这里 l = 0, r = len(nums)-1

3. 循环采用左闭右闭形式，每次都能检测到左右边界

35 搜索插入位置

1. 遍历数组，如果当前值小于目标值则继续

2. 如果当前值等于目标值则直接返回 idx

3. 如果当前值大于目标值则直接返回 idx，表示当前位置即为插入位置

4. 遍历结束，则说明目标值大于数组全部的数字，插入到最后位置

34 在排序数组中查找元素的第一个和最后一个元素

1. 基于二分快速定位到目标值，如果返回 -1，则表示数组中该值不存在

2. 在二分找到的基础上，如果左侧值不等于目标值，则为第一个 idx

1. 基于二分快速定位到目标值，如果返回 -1，则表示数组中该值不存在

2. 在二分找到的基础上，如果右侧值不等于目标值，则为最后一个 idx

69 x 的平方根

367 有效的完全平方数