69.x的平方根
题目描述：
方法一：二分查找：
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;//-1是想实现向下取整
//也可以写成：int mid=(l+r)/2.0
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
};
这里在二分法中，需要注意的是：
(1)mid的更新方式，具体是（l+r）/2.0还是（l+r-1）/2等等，根据具体需要决定；
(2)while中的条件语句：实验过，当使用while(l<r)时就无法通过，也就是说一定需要l>r时才可以跳出这个循环，因为当l=r时有可能还没有找到最终的ans，如果需要再次调整l，则这个才是ans
(3)更新ans的时机：修改l的时候就记录一下，最后一个记录的值就是真的ans；
方法二：牛顿迭代法
class Solution {
public:
int mySqrt(int a) {
long x = a;
while (x * x > a) {
x = (x + a / x) / 2;
}
return x;
}
};
二分法，代码如下：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty())return vector<int>{-1,-1};
int lower=lower_bound(nums,target);
int upper=upper_bound(nums,target)-1;
if(lower==nums.size()||nums[lower]!=target){
return vector<int>{-1,-1};
}
return vector<int>{lower,upper};
}
int lower_bound(vector<int>&nums,int target){
int l=0,r=nums.size(),mid;
while(l<r){
mid=(l+r)/2;
if(nums[mid]>=target){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
int upper_bound(vector<int>&nums,int target){
int l=0,r=nums.size(),mid;
while(l<r){
mid=(l+r)/2;
if(nums[mid]>target){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
};
二分查找中还是对一些细节不是非常理解，比如什么时候要用等号，什么时候要加一…
题目描述：
思路：使用二分查找的思路，但是二分的前提就是需要一个sorted的序列，所以首先需要判断排好序的数组；
首先将mid对应的元素与右端相比较，≤右端值时，说明mid到r之间的数组是增序排列的，可以直接使用二分查找（当然是target在区间内的，否则只能在左区间查找）；大于右端值时，说明左区间是排好序的，用类似思路可以解决；
当遇到上述target处于非增序部分时，就可以递归地解决问题，因为舍弃掉排序区间后，得到的还是一个翻转数组，可以递归地解决这个问题；
class Solution {
public:
bool search(vector<int>& nums, int target) {
int start=0,end=nums.size()-1;//定义头尾
while(start<=end){
int mid=(start+end)/2;
if(nums[mid]==target){
return true;
}
if(nums[start]==nums[mid]){
//无法判断哪个区间是增序的
++start;
}else if(nums[mid]<=nums[end]){
//右区间是增序的
if(target>nums[mid]&&target<=nums[end]){
//如果target在这个区间中
start=mid+1;//修改区间
}else{
end=mid-1;
}
}else{
//左区间是增序的
if(target>=nums[start]&&target<nums[mid]){
end=mid-1;
}else{
start=mid+1;
}
}
}
return false;
}
};
