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从右边找过来。