网站目录在哪里,中国建筑信息平台,可信网站认证收费,网络规划设计师教程第2版下载x 的平方根 在0~X中肯定有数的平方大于X#xff0c;这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增#xff0c;它们的平方也是递增的#xff0c;这样我们就可以用二分查找。 我们找出的数的平方是或者恰好X#xff0c;所以把0~X的平方分为X … x 的平方根 在0~X中肯定有数的平方大于X这是肯定的。我们需要从中找出一个数的平方最接近X且不大于X。0~X递增它们的平方也是递增的这样我们就可以用二分查找。 我们找出的数的平方是或者恰好X所以把0~X的平方分为X X的两部分求区间的最右端 class Solution {
public:int mySqrt(int x) {long long left0,rightx;while(leftright){long long midleft(right-left1)/2;if(mid*midx) leftmid;else rightmid-1;}return left;}
}; long long防止超出int范围 搜索插入位置 递增数组找到相等返回下标反正按顺序插入恰好比target大的值也就是目标值target。把区间分为target target找右区间左端 class Solution {
public:int searchInsert(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target) leftmid1;else rightmid;}if(nums[left]target) left;//left恰好是数组最后一个元素return left;}
};
山脉数组的峰顶索引 这段数组可以分成两部分前一部分递增 后一部分递减。 这样我们就可以用二分查找如果mid处于递增位置那么目标值肯定在右边。反之左边。 下面有两种做法不同点在于把峰值看做是递增数组上还是递减数组上在递增数组就是求右端点在递减数组就是求左端点。 峰值属于递减数组求左端点
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left0,rightarr.size()-1;while(leftright){int midleft(right-left)/2;if(arr[mid]arr[mid1]) rightmid;else leftmid1;}return left;}
}; 因为mid可能正好是目标值不能跟后面的值比较后面是递增数组的。 峰值属于递增数组求右端点
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left0,rightarr.size()-1;while(leftright){int midleft(right-left1)/2;if(arr[mid]arr[mid-1]) leftmid;else rightmid-1;}return left;}
};
寻找峰值 有三中情况一直递增 / 一直递减 \ 既有递增又有递减 /\/\/\/\ 但无论那种情况如果是递增那它的右边一定有峰值如果递减它的左边一定有峰值。 class Solution {
public:int findPeakElement(vectorint nums) {int left0,rightnums.size()-1;while(leftright){int midleft(right-left1)/2;if(nums[mid]nums[mid-1]) leftmid;else rightmid-1;}return left;}
}; 把峰值看作递增的部分如果nums[mid]nums[mid-1]说明递增那么mid可能是峰值所以left不能mid1,leftmid,让right从右边找过来。
