【优选算法 二分查找】二分查找算法入门详解：二分查找小专题

     

 

---

  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； 

---

    编写代码    

---

 

可以把两种特殊的情况合并成一种：

---