基本的二分法的架构如下代码块所示：
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;//这与(left + right) / 2 的结果相同，只是为了防止太大导致溢出
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = mid + 1;//注意，middle已经寻找过了，为此要避开
} else if (nums[mid] > target) {
right = mid - 1;//注意，middle已经寻找过了，为此要避开
}
}
return ...;
}
1.寻找一个数
最直接的解法用find函数,时间复杂度应该是O（N），空间复杂度为O（1）
class Solution {
public:
int search(vector<int>& nums, int target) {
auto result=find(nums.begin(),nums.end(),target);
if (result<nums.end())
return result-nums.begin();
return -1;
}
};
二分法：时间复杂度为O(logn)，空间复杂度为O（1）
class Solution {
public:
int search(vector<int>& nums, int target) {
//已经排序好的了
int left=0, right=nums.size()-1;
while(left<=right)//注意有等号，由于right的初始化，决定了采用的实际上是闭区间
{
int middle=(left+right)/2;
if(nums[middle]==target)
return middle;
else if(nums[middle]>target)//证明target在左半区
right=middle-1;//注意：由于搜索区间是闭区间，[left, mid-1]
else if(nums[middle]<target)
left=middle+1;//注意，[mid+1, right]
// mid已经搜索过了，不避开会导致超时~
}
return -1;
}
};
若上题while(left<=right)改为while(left<right)则应该是：
while(left <= right) 的终止条件是 left == right + 1（也就是left>right），写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，
可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，
这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。必须再次检查最后一个索引！
2. 左侧边界与右侧边界的二分法查找
要解决这道题，明确以下三种二分法的思路(这个所谓的思路感觉有点问题~按着做容易出错，还是以上题为架构看如何逼近边界较好)
Click to expand the code,时间复杂度： O(logn),空间复杂度：O(1)
class Solution {
public:
int left_bound(vector<int>& nums, int target)
{
int left=0, right=nums.size()-1;
while(left<=right)
{
int mid=(left+right)/2;
int value=nums[mid];
if(value<target)//target应该在右半区
left=mid+1;//中间已经算过了
else if(value>target)//应该在左半区
right=mid-1;//中间已经算过了
else if(value==target)
right=mid-1;//一直递推收紧右侧的边界以锁定左侧边界，
// 下一个中间值必然是大于或等于，因此可以做到锁定一直更新right
}
// 注意要先判断是否有数据越界的情况（由于上面right在找到目标后递推，故此有可能left越界）
if(left<0 || left>=nums.size())
return -1;
// 判断一下 nums[left] 是不是 target（由于上面right在找到目标后递推，故此有可能left不是目标值但是结束了~）
return nums[left] == target ? left : -1;
}
int right_bound(vector<int>& nums, int target)
{
int left=0, right=nums.size()-1;
while(left<=right)
{
int mid=(left+right)/2;
int value=nums[mid];
if(value<target)//target应该在右半区
left=mid+1;//中间已经算过了
else if(value>target)//应该在左半区
right=mid-1;//中间已经算过了
else if(value==target)
left=mid+1;//一直地推左侧以锁定右侧的边界
// 下一个中间值，必然是小于等于，因此一直推直到锁定右边
}
// 确保不要越界
if(right<0 || right>=nums.size())
return -1;
// 判断一下 nums[right] 是不是 target
return nums[right] == target ? right : -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
// 左侧边界与右侧边界的二分法查找
int left=left_bound(nums,target);
if(left==-1)//左边界若不合法，就不用判断右边了~
return vector<int>{-1,-1};
int right=right_bound(nums,target);
return vector<int>{left,right};
}
};
求解立方根
Click to expand the code。关键点在于要考虑负号以及小数的情况。且浮点数left<=right会无限运行，需要给个小范围的阈值
寻找两个正序数组的中位数
Click to expand the code。最直接的做法其实就是合并一个数组，然后排序，但是时间复杂度为：O((M+N)Log(M+N))其实并不满足题目要求（虽然可以通过所有测试样例）
Click to expand the code，下面的双指针法可以让时间复杂度进一步降低为O（m+n）
Click to expand the code。而题目要求O(Log(M+N))实际上就是典型的二分法的时间复杂度。
思路就是在两个有序数组中找到第k 小的元素。其中k就是中位数。（理解得不是很透彻～）