【算法刷题指南】二分查找

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站

704. 二分查找

704.二分查找

解法1

• 暴力
• 遍历数组
• 当遍历到数组中元素等于target时，返回下标
• 遍历完成后没有在数组中找到target，返回-1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==target) return i;
        }
        return -1;
    }
};

解法2

• 数组升序，找其中一个值，二分查找
• 定义两个指针，左指针和右指针，分别初始化为0和nums.size()-1
• 如果中间值大于target，将右指针移到mid-1位置
• 如果中间值小于target，将左指针移到mid+1位置
• 中间值等于target直接返回下标mid
• 没有找到则返回-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) / 2;
            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};

35.搜索插入位置

35.搜索插入位置

• 二分查找
• mid<target ，则left=mid+1
• mid>=target ，则right=mid

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

69.x的平方根

69.x的平方根

• 二分查找
• 注意题目给的数范围，不能使用int型
• 常规二分查找操作

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

852. 山脉数组的峰顶索引

852. 山脉数组的峰顶索引

• 二分查找
• 计算mid：
  • 如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；
  • 如果 mid 位置呈现下降趋势，说明我们接下来要在[left, mid - 1] 区间搜索；
  • 如果mid位置就是⼭峰，直接返回结果

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

162.寻找峰值

162.寻找峰值

• 二分查找
• 本题和[山脉数组的峰顶索引]类似，但是这道题会存在多个峰值，考虑到二段性即可用二分查找
• nums[mid]>nums[mid+1]说明mid的左边肯定是递减的，只要在左边找峰值即可，也就是让right=mid
• nums[mid]<=nums[mid+1]说明mid]右侧肯定是递增的，只要在右边找峰值即可，也就是让left=mid+1

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]) right=mid;
            else left=mid+1;
        }
        return left;
    }
};

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

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

• 二段性使用二分查找

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

LCR173.点名

LCR173.点名

• 二分查找
• 如果mid处缺少：
  • mid左侧值等于下标
  • mid右侧值不等于下标

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;
        }
        return left==records[left]?left+1:left;
    }
};