一、二分查找算法思路总结

大家先看总结，然后再根据后面的题型去慢慢领悟

二、二分查找（easy）

思路：（模版1）正常的二分查找策略

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target)  left=mid+1;
            else if(nums[mid]>target)  right=mid-1;
            else return mid;
        }
        return -1;
    }
};

三、在排序数组中查找元素的第一个位置和最后一个位置

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

 要注意示例3提到的边界情况！！

思路：找第一个，用左区间端点查找（模版2），找最后一个，用右端点区间查找（模版3）

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        if(nums.size()==0)  return {-1,-1};//处理边界情况，否则会越界
        int begin=0;
        //区间左端点
           int left=0,right=nums.size()-1;
           while(left<right)
          {
            int mid=left+(right-left)/2;
            if(nums[mid]<target) left=mid+1;
            else right=mid;//最后会落在区间的左端点
          }
          if(nums[left]!=target) return{-1,-1};//找不到
          else begin=left;
        //区间右端点
          right=nums.size()-1;
           while(left<right)
          {
            int mid=left+(right-left+1)/2;
            if(nums[mid]<=target) left=mid;//最后会落在区间的右端点
            else right=mid-1;
          }
        return {begin,right};//此时至少有一个左端点，所以不可能找不到。
    }
};

四、x的平方根

x的平方根

思路：右端区间二分查找法

class Solution {
public:
    int mySqrt(int x) 
    {
        if(x<1) return 0;//处理边界情况
        int left=1,right=x/2;
        while(left<right)
        {
            long long mid=left+(right-left+1)/2;
            if(mid*mid>x) right=mid-1;
            else  left=mid;
        }
        return left;
    }
};

 五、搜索插入位置

搜索插入位置

思路1：左端区间查找 

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target) left=mid+1;
            else right=mid;
        }
        if(nums[left]<target) return left+1;
        return left;
    }
};

思路2：右端区间查找（有特殊情况，比如正好是和targe相等且只有一个元素）

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]<target) left=mid;
            else right=mid-1;
        }
        //右端区间要考虑边界情况（特殊情况，只有一个元素且正好等于target）
        if(nums[left]>=target) return left;
        return left+1;
    }
};

 六、山峰数组峰顶的索引

山峰数组峰顶的索引

本题特别的就是不再是升序，而是去找二段性的规律

思路1：左端区间查找 

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr)
    {
          int left=1,right=arr.size()-2;
          while(left<right)
          {
            int mid=left+(right-left)/2;
             if(arr[mid]<arr[mid+1])  left=mid+1;
             else right=mid;   
          }
          return left;
    }
};

思路2：右端区间查找 

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr)
    {
          int left=1,right=arr.size()-2;
          while(left<right)
          {
            int mid=left+(right-left+1)/2;
             if(arr[mid]>=arr[mid-1])  left=mid;
             else right=mid-1;   
          }
          return left;
    }
};

七、寻找峰值

寻找峰值

 左区间端点法：

class Solution {
public:
    int findPeakElement(vector<int>& nums) 
    {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[mid+1]) left=mid+1;
            else right=mid;
        }
        return right;
    }
};

右区间端点法：

class Solution {
public:
    int findPeakElement(vector<int>& nums) 
    {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]>=nums[mid-1]) left=mid;
            else right=mid-1;
        }
        return right;
    }
};

 八、点名

点名

左区间端点法 

class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
           int left=0,right=records.size()-1;
           while(left<right)
           {
            int mid=left+(right-left)/2;
            if(records[mid]==mid)   left=mid+1;
            else  right=mid;
           }
           if(records[right]==right)  return right+1;
           else return right;
    }
};

注意：插入元素的时候要注意是否是在最右边插入！

九、 寻找旋转数组中的最小值

寻找旋转数组中的最小值

思路：左区间端点查找法

class Solution {
public:
    int findMin(vector<int>& nums) 
    {
       int left=0,right=nums.size()-1;
        int target=nums[right];//标记一下
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>target) left=mid+1;
            else right=mid;
        }
        return nums[left];
    }
};

十、二分查找规律的再总结

       二分查找的策略基本上都是去找一个数，对应的有三种模版：正常的二分查找、左区间端点查找、右区间端点查找。其中正常的二分查找局限性比较大，必须得是升序且限制条件较多，大多数情况下不符合题意。最常用的就是左区间端点（关键是left会大跳跃，且目标位置在较大值区间的左边）和右区间端点法（关键是right会大跳跃，且目标位置在较小值区间的右边）。