二分查找_ x 的平方根&&搜索插入位置&&山脉数组的峰顶索引

 x 的平方根 

在0~X中肯定有数的平方大于X,这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增,它们的平方也是递增的,这样我们就可以用二分查找。

我们找出的数的平方是<或者恰好==X,所以把0~X的平方分为<=X >X的两部分,求<=区间的最右端

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

long long防止超出int范围

搜索插入位置

递增数组,找到相等返回下标,反正按顺序插入(恰好比target大的值),也就是目标值>=target。把区间分为<target >=target,找右区间左端

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) left++;//left恰好是数组最后一个元素
        return left;
    }
};

山脉数组的峰顶索引

这段数组可以分成两部分,前一部分递增 后一部分递减。

这样我们就可以用二分查找,如果mid处于递增位置,那么目标值肯定在右边。反之,左边。

下面有两种做法,不同点在于把峰值看做是递增数组上还是递减数组上,在递增数组就是求右端点,在递减数组就是求左端点。

峰值属于递减数组,求左端点

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

因为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;
    }
};

寻找峰值

有三中情况一直递增 / 一直递减 \ 既有递增又有递减 /\/\/\/\

但无论那种情况,如果是递增那它的右边一定有峰值,如果递减它的左边一定有峰值。

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

把峰值看作递增的部分,如果nums[mid]>nums[mid-1]说明递增,那么mid可能是峰值,所以left不能=mid+1,left=mid,让right从右边找过来。

上一篇:[ComfyUI]Flux:爆火禅语小和尚素材!禅意人生,享受自在


下一篇:List线性表