【优选算法 二分查找】二分查找算法入门详解：二分查找小专题
x 的平方根
题目解析
算法原理
解法一： 暴力解法
如果要求一个数(x)的平方根，可以从 0 往后枚举，直到有一个数(a)，a^2<=x，(a+1)^2>x，a即为所求；
解法二：二分查找
分析二段性
因为暴力枚举的数字从1开始递增，所以枚举的数是有序的，并且能以 a 为边界点，把枚举的数组分成两个部分 ：
因为这道题分 a^2<=x，a^2>x 两种情况，而不是分成三种情况，所以使用不朴素的二分查找；
left 初始化为1，right 的初始化需要商榷，所以以 mid 的值对应的 a^2 和 x 的大小关系进行讨论 ：
- 1. a^2 <= x
- 2. a^2 > x
处理细节问题
根据范围，我们可以发现 x 是可以小于1的，如果当 x=0.5之类的小数，那么开根号得到的数的整数部分一定是0，所以当 x<1，直接返回0即可；所以 left 初始化为1
编写代码
搜索插入位置
题目解析
算法原理
解法：二分查找
查找二段性
通过下面的例子可以发现，插入的位置要么是第一个大于 target 的数的下标，要么是 target 大于数组中所有元素，而被插入到末尾：
所以插入 target 的位置特点是第一个大于等于 target 的元素下标，这个下标即为返回值，所以有如下二段性：
left 和 right 的更新策略
分析 mid 落在上面两个区间时，left 和 right 的更新策略 ：
- 1.mid >= target
- 2.mid < target
编写代码
山脉数组的峰顶索引
题目解析
算法原理
如果要找峰顶元素的下标，那么第一个元素和最后一个元素其实是不需要考虑的；
解法一：暴力枚举
定义一个指针，从起始位置开始往后扫描，当扫描到一个元素的值大于后面一个元素的值，就返回这个元素的下标，时间复杂度为O(N);
解法二：二分查找
分析二段性
我们发现，哪怕这个数组并不是有序的，依旧可以使用二分查找，就是因为数组具有二段性；
left 和 right 的更新策略
分析 mid 落在上面两个区间时，left 和 right 的更新策略 ：
- 1. arr[mid] > arr[mid-1]
- 2. arr[mid] < arr[mid-1]
编写代码
寻找峰值
题目解析
算法原理
- 如果起始位置是呈现下降趋势的，就直接返回起始位置下标0即可，因为nums[-1]为负无穷；
- 如果刚开始往后遍历，一直是上升，直到峰值后下降，返回峰值下标：
- 当遍历完所有数组，都是呈上升趋势，返回最后一个元素下标即可，因为nums[length]为无穷小
解法一：暴力枚举
定义一个指针直接往后扫描，根据上面的三种情况作出相应的处理即可；时间复杂度是考虑最坏的情况，如第三种情况，所以为O(N)
解法二：优化暴力解法，二分查找
分析二段性
我们分析数组任意区间相邻两个点的情况：
- 1. nums[i] > nums[i+1] ，在[0,i] 区间一定存在至少一个峰值，接下来可以去 [0,i] 区间找：
- 2. nums[i] < nums[i+1]，在 [i+1,length-1] 区间至少存在一个峰值，所以可以去这个区间找：
所以根据 nums[i] 与 nums[i+1] 的关系，把数组分成了两部分，去其中一个部分查找结果；
刚刚在山峰数组中找索引，还算不上严格的无序；这道题是严格的无序，但是依旧能使用二分查找解决，说明二段性是决定一个题能否使用二分查找的必要条件；
left 和 right 的更新策略
根据 arr[mid] 和 arr[mid+1] 的关系，更新left 和right;
- 1. arr[mid] > arr[mid+1] ，在[0,mid] 区间一定存在至少一个峰值：
- 2. arr[mid] < arr[mid+1]，在 [i+1,length-1] 区间至少存在一个峰值：
编写代码
暴力枚举
二分查找
寻找旋转排序数组中的最小值
题目描述 
算法原理
经过旋转的数组有什么特性呢？
因为数组元素是互不相同的，所以折线图又可以分成两部分：
左边部分严格在nums的分界线上面，右边部分严格在nums分界线下面，并且两个折线部分都是递增的；
解法一：暴力枚举
从前往后扫描数组，直到找到最小值；时间复杂度O(N)；暴力解法慢就慢在没有利用旋转数组能分成两个递增折线，且左边严格高于右边的特性；
解法二：二分查找
分析二段性
如果把问题抽象成折现图，那么就会发现这个数组有明显的二段性，数组的两个部分被分界线严格划分； 对于AC，nums[i] > nums[length-1]；对于DE，nums<=nums[length-1];
注意：本题的特殊之处，是拿中间元素的值和末尾元素的值的大小关系，来分成两个区间
所以要找最小值，我们只需要找到下标分割线所在的位置，即是最小值下标位置，所以就是查找右边区域的左端点；
left 和 right 的更新策略
分析 mid 落在上面两个区间时，left 和 right 的更新策略 ：
注意，这个数组是经过有序递增数组旋转得到的数组，这就避免了很多边界情况的讨论，旋转数组的值分布一定是分成两个递增折线，并且左边折线严格都大于右边；
- 1. AC：nums[mid] > nums[length-1]
- 2. DF：nums[mid] <= nums[length-1]
上面是以末尾元素为参照物，我们可以选起始元素为参照点吗？
我们发现，AC区间是严格大于nums[0] 的，CD区间也是严格小于 nums[0] 的，也具有二段性；
编写代码
0~n-1中缺失的数字
题目描述
算法原理
解法一：哈希表
如果是n个数字，就建 n+1个桶的哈希表，遍历原始数组并且填入哈希表，最后找出 val=0 的key即可；时间复杂度为 O(N)，但是还要利用O(N)的空间复杂度
解法二：直接遍历
从前往后直接遍历，时间复杂度为 O(N)；
解法三 ：位运算
异或 ^ ，把缺失元素的数组，和完整数组的每一个元素进行异或操作：
异或有一个特性，就是相同元素相互抵消，最终异或结果就是缺失的数；
时间复杂度为 O(N)
解法四：数学方法（高斯 / 等差数列求和公式）
因为数组是一个等差升序数组，就是一个等差数列，把完整的数组通过等差数列求和公式求出，再依次减去缺失数字的数组，即可得到缺失的元素；时间复杂度为 O(N)
解法五：二分查找
分析二段性
我们把缺失元素的数组下标标注出来，帮助我们发现二段性：
此时，我们发现，数组可以分成两个区域，下标和元素一 一对应是一个区域，不是一 一对应，则是类外一个区域，因此，这个数组就有二段性；
left 和 right 的更新策略
如果下标和元素对应，left=mid+1，不能对应则 right = mid；
编写代码
可以把两种特殊的情况合并成一种：
