基本的二分法的架构如下代码块所示：
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)则应该是：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0, right =nums.size()-1;
while(left<right)
{
int middle=(left+right)/2;
if(nums[middle]<target)
{
left=middle+1;
}
else if(nums[middle]>target)
{
right=middle-1;
}
else
return middle;
}
return nums[left]==target? left:-1;
}
};
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. 左侧边界与右侧边界的二分法查找
要解决这道题，明确以下三种二分法的思路(这个所谓的思路感觉有点问题~按着做容易出错，还是以上题为架构看如何逼近边界较好)
,时间复杂度： 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};
}
};
求解立方根
关键点在于要考虑负号以及小数的情况。且浮点数left<=right会无限运行，需要给个小范围的阈值
#include <iomanip>
#include <iostream>
#include <cmath>
using namespace std;
int main() {
double value;
cin>>value;
//二分法
//由于是开立方根，所以存在为负号的情况
//同时需要考虑小数的情况
double left=min(-1.0, value);
double right=max(1.0, value);
double middle;//就是结果
// while(left<=right)//由于是浮点数，为此永远都很接近不会相等
while(abs(right-left)>0.01)//因此给0.01。毕竟小数点保留1位而已（注意是相减大于某个小数）
{
middle=(left+right)/2.0;
double result=pow(middle,3);
if(result<value)
{
left=middle;
}
else if(result>value)
{
right=middle;
}
else//相等
break;
}
std::cout<<fixed<<setprecision(1)<<middle;
}
寻找两个正序数组的中位数
最直接的做法其实就是合并一个数组，然后排序，但是时间复杂度为：O((M+N)Log(M+N))其实并不满足题目要求（虽然可以通过所有测试样例）
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> new_group;
for(int i=0;i<nums1.size();i++)
{
new_group.push_back(nums1[i]);
}
for(int i=0;i<nums2.size();i++)
{
new_group.push_back(nums2[i]);
}
// 时间复杂度为：O((M+N)Log(M+N))
sort(new_group.begin(),new_group.end());
if((nums1.size()+nums2.size())%2==0)//能被偶数整除(余数)
return (double)(
new_group[(nums1.size()+nums2.size())/2]+
new_group[(nums1.size()+nums2.size())/2-1]
)/2;
return new_group[(nums1.size()+nums2.size())/2];//奇数的情况返回原值
}
};
，下面的双指针法可以让时间复杂度进一步降低为O（m+n）
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> merged;
int i = 0, j = 0;
// 合并两个有序数组
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] < nums2[j]) {
merged.push_back(nums1[i]);
i++;
} else {
merged.push_back(nums2[j]);
j++;
}
}
// 将剩余元素添加到合并数组
while (i < nums1.size()) {
merged.push_back(nums1[i]);
i++;
}
while (j < nums2.size()) {
merged.push_back(nums2[j]);
j++;
}
// 计算中位数
int n = merged.size();
if (n % 2 == 1) {//为奇数
return merged[n / 2];
} else {//为偶数
return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
}
}
};
而题目要求O(Log(M+N))实际上就是典型的二分法的时间复杂度。
思路就是在两个有序数组中找到第k 小的元素。其中k就是中位数。（理解得不是很透彻～）
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 确保nums1是较短的数组，以减少二分查找的范围
if (nums1.size() > nums2.size())
swap(nums2, nums1);
int m = nums1.size();
int n = nums2.size();
int k = (m + n + 1) / 2;//第k小的值
int left = 0, right = m;
while (left < right) {
//i和j为nums1 和 nums2 中的分割点
// k为中位数左侧元素的总数
// num1中的分割点
int i = (right +left) / 2;
//num2中的分割点
int j = k - i;//第k小的值，对应1中的i个，那么2中就是k-2个
if (nums1[i] < nums2[j - 1]) {
left = i + 1; // i太小了，需要右移
} else {
right = i; // i太大了，需要左移
}
}
int i = left;
int j = k - i;
int nums1LeftMax = (i == 0 ? INT_MIN : nums1[i - 1]);
int nums1RightMin = (i == m ? INT_MAX : nums1[i]);
int nums2LeftMax = (j == 0 ? INT_MIN : nums2[j - 1]);
int nums2RightMin = (j == n ? INT_MAX : nums2[j]);
// 如果总长度是奇数
if ((m + n) % 2 == 1) {
return std::max(nums1LeftMax, nums2LeftMax);
} else {
// 如果总长度是偶数
return (std::max(nums1LeftMax, nums2LeftMax) + std::min(nums1RightMin, nums2RightMin)) / 2.0;
}
}
};