优选算法之二分查找

一，简介

二分查找是细节比较多的，但是你理解细节那么二分查找可以直接秒杀的。二分查找是必须有序才能用吗？答案显然是不太正确的。更准确的说是具有二段性便可以使用二分查找，而且二分查找是有模板的。接下来我将会介绍一些二分查找的类型题目，来帮助大家理解并快速上手二分查找。

二，模板类型

二分查找分为三个模板类型，分别是朴素二分模板，寻找左区间的二分模板，寻找右区间的二分模板。

就拿这一题来讲解朴素模板：704.二分查找 

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

总结：

朴素模板一般不常用记忆即可。

这一题讲解左右端点模板：在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
 
        int left = 0, right = nums.size() - 1;
 
        int begin, end;
//细节处理如果数组为空，返回-1，-1
        if (nums.size() == 0)
        {
            return { -1,-1 };
        }
//进入循环条件
        while (left < right)
        {
//写出中间值
 
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
 
            }
        }
//判断数组左端点
 
        if (nums[left] == target)
        {
            begin = left;
        }
        else //没有则直接返回-1，-1
        {
            return { -1,-1 };
        }
//判断数组右端点
        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;
            }
        }
 
        return { begin,right };
    }
};

模板总结：

只要写出左右端点模板即可完成编码，当判断左右端点时，如果是mid+1则mid为left+（right-left）/2，如果是mid-1则mid为left+（right-left+1）/2。

三，例题

其它代码分类讨论，接下来我就带大家熟悉二分模板。

例题：35.搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
//进入循环条件
        while(left<right)
        {
//根据左右端点判断mid
            int mid=left+(right-left)/2;
//判断左端点
            if(nums[mid]<target)
            {
                left=mid+1;
            }
            else
            {
                right=mid;
            }
        }
//处理细节，如果没有则插入最后一个位置
        if(nums[left]<target)
        {
            return left+1;
        }
        else
        {
            return left;
        }
    }
};

例题：x的平方根

class Solution {
public:
    int mySqrt(int x) {
//处理细节，x小于1，0的平方为0
if(x<1)
{
    return 0;
}
//x大于等于1
int left=1,right=x;
while(left<right)
{
//判断右端点
    long long mid=left+(right-left+1)/2;
    if(mid*mid<=x)
    {
        left=mid;
    }
    else
    {
        right=mid-1;
    }
}
return right;
    }
};

例题： 

​​​​​​山脉数组的峰顶索引

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

总结：这个题就很好表达了二分查找的使用有序并不是必要条件

例题：

寻找峰值

和上一题一样找清楚判断左右端点对于mid的关系

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 left;
    }
};

例题： 

寻找旋转排序数组中的最小值

该题需要了解数组是怎样旋转的，分为ab，cd两个段。如果第一个值大于最后一个说明最小值在cd段，反之在ab段，这样就可以判断left和right怎么变化。

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

例题：

点名

该题因为不限制时间所以有多种解法

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int n=records.size();
        int left=0,right=n-1;
        
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(records[mid]==mid)
            {
                left=mid+1;
            }
            else
            {
                right=mid;
            }
        }
//处理细节问题，如果是最后一个数确实需要加1
        if(records[left]==left)
        {
            left++;
            return left;
        }
        else
        {
            return left;
        }
 
    }
};