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

南桥

发布于 2025-02-07 09:55:29

1180

文章被收录于专栏：南桥谈编程南桥谈编程

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.搜索插入位置

二分查找
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的平方根

二分查找
注意题目给的数范围，不能使用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. 山脉数组的峰顶索引

二分查找
计算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.寻找峰值

二分查找
本题和[山脉数组的峰顶索引]类似，但是这道题会存在多个峰值，考虑到二段性即可用二分查找
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.寻找旋转排序数组中的最小值

二段性使用二分查找

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.点名

二分查找
如果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;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除

指针