何为二分查找？
一个有序数组，然后两个指针，一个指向第一个left，一个指向最后一个right，然后计算mid。如果mid值大于指定值，那就right指向mid-1。如果小于则left指向mid+1.
69.x的平方根
69. x 的平方根
题目
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <=- 1
题解
这个题目还是比较简单，有直接可以调用的库。class Solution { public:int mySqrt(int x) {int t=sqrt(x);return t;} };但是如果使用二分查找，应该如何解决问题呢。
首先求a的平方根，那么结果一定是在[1,a]之间。
这是一个有序数组。所以我们就可以使用二分查找。
class Solution { public:int mySqrt(int x) {long long i=0;long long j=x/2+1;//对于一个非负数n，它的平方根不会大于（n/2+1）while(i<=j){long long mid=(i+j)/2;long long res=mid*mid;if(res==x) return mid;else if(res<x) i=mid+1;else j=mid-1;}return j;} };
34.在排序数组中查找的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
题目
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [5,7,7,8,8,10] , target = 8 输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10] , target = 6 输出：[-1,-1]示例 3：
输入：nums = [], target = 0 输出：[-1,-1]提示：
0 <= nums.length <=<= nums[i] <=
nums是一个非递减数组
题解
在一个递增的数组中找target，找到数组中的第一个位置和第二个位置。
在这里可以使用二分查找的方法。
通过类似的方法，找到一个下限和一个上限。
如果mid的值大于等于target，那就right=mid。否则left=mid+1。
找最后一个位置（上限）的不同之处就是，如果mid大于target，那就right=mid。否则left=mid+1.
找第一个位置，就是尽量往左查找，所以mid的值等于target，right不变
找最后一个位置，就是尽量往右查找，所以mid的值等于target时，left+1.
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0)return vector<int>{-1,-1};int lower_=lower(nums,target);int high_=high(nums,target)-1;if(lower_==nums.size()||nums[lower_]!=target)return vector<int>{-1,-1};return vector<int>{lower_,high_};}int lower(vector<int> &nums,int target){int l=0,r=nums.size();while(l<r){int mid=(r+l)/2;if(nums[mid]>=target)r=mid;elsel=mid+1;}return l;}int high(vector<int> &nums,int target){int l=0,r=nums.size();while(l<r){int mid=(r+l)/2;if(nums[mid]>target)r=mid;elsel=mid+1;}return l;}
};81.搜索旋转排序数组Ⅱ
81. 搜索旋转排序数组 II
题目
已知存在一个按非降序排列的整数数组
nums，数组中的值不必互不相同。在传递给函数之前，
nums在预先未知的某个下标k（0 <= k < nums.length）上进行了 旋转 ，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,4,4,5,6,6,7]在下标5处经旋转后可能变为[4,5,6,6,7,0,1,2,4,4]。给你 旋转后 的数组
nums和一个整数target，请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums中存在这个目标值target，则返回true，否则返回false。你必须尽可能减少整个操作步骤。
示例 1：
输入：nums =[2,5,6,0,0,1,2], target = 0输出：true示例 2：
输入：nums =[2,5,6,0,0,1,2], target = 3输出：false提示：
1 <= nums.length <= 5000-<= nums[i] <=
- 题目数据保证
nums在预先未知的某个下标上进行了旋转-
题解（测试点275/282)
旋转排序数组，也就是排好序的数组首尾相连，然后从中间随机断开。从断开这里分开，两段都是有序的。
一开始思考的方向是，找到最大值，然后从最大值处断开。分两段进行查找。
但是这里有一个问题，就是可能出现多个最大值，如[2,2,2,0,1]
断开后就变成[2],[2,2,0,1]
class Solution { public:bool search(vector<int>& nums, int target) {int n=max_element(nums.begin(),nums.end())-nums.begin();int l1=0,r1=n;int l2=n+1,r2=nums.size()-1;while(l1<=r1){int m1=(l1+r1)/2;if(nums[m1]<target)l1=m1+1;else if(nums[m1]>target)r1=m1-1;elsereturn true;}while(l2<=r2){int m2=(l2+r2)/2;if(nums[m2]<target)l2=m2+1;else if(nums[m2]>target)r2=m2-1;elsereturn true;}return false;} };正确题解
可以根据二分查找的方法，当mid与target值相等就返回true。
在查找过程中首先判断mid的值和target是不是相同，相同的话就要继续start++，这里就是解决之前所说的会有多个相同的数据，说明这里还不是我们的分割点。
如果不等于的话，可能会出现一部分是递增，另外一部分不是。这个时候我们就判断是否那一段是有序的，并且对那一段进行相应的判断。根据判断进行start和end的变化。
class Solution { public:bool search(vector<int>& nums, int target) {int start=0,end=nums.size()-1;int mid;while(start<=end){mid=(start+end)/2;if(nums[mid]==target)return true;if(nums[start]==nums[mid])start++;else if(nums[mid]<=nums[end]){if(nums[mid]<target&&nums[end]>=target)start=mid+1;else end=mid-1;}else{if(nums[mid]>target&&nums[start]<=target)end=mid-1;else start=mid+1;}}return false;} };