二分查找用于在一个单调序列中查找指定的值，根据查找的方式，二分查找具有不同的变体，但是无论如何，其基本模板为：
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
}下面讨论对于单调非递减序列中查找指定值的方式。这里的“单调非递减”意味着序列是单调递增的，但是值可能有重复。
二分查找有三个变体：
查找指定的值
最常见的查找方式是在单调递增的序列 \([left, right]\) 中查找指定的值。
简易流程如下：
在 \([left, right]\) 中查找值为 target 对应的索引。
若 \(nums[mid] == target\)，则返回 \(mid\)。
若 \(nums[mid] < target\)，则在 \([left, mid)\) 中查找，否则在 \((mid, right]\) 中查找。
这里注意 \([left, mid)\) 代表的区间实际上就是 \([left, mid - 1]\)。
相应的，\((mid, right]\) 实际上就是 \([mid, right]\)
考虑到当 \(left == right\) 时依然有一个值未检查到，因此结束条件为 \(left > right\)。也就是循环条件为 \(left <= right\)。
最终实现为：
class Solution {
public:
// 标准的二分搜索框架，搜索目标元素的索引，若不存在则返回 -1
int search(vector<int>& nums, int target) {
int left = 0;
// 注意
int right = nums.size() - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// 注意
left = mid + 1;
} else if (nums[mid] > target) {
// 注意
right = mid - 1;
}
}
return -1;
}
};查找左侧边界
在查找左侧边界的时候根本思想为在找到 target 值时不要返回，而是不断收缩右侧边界，直至将区间收缩到 1：
在 \([left, right]\) 中查找值为 target 对应的索引。
若 \(nums[mid] == target\)，则将区间收缩至 \([left, mid)\)。
若 \(nums[mid] < target\)，则在 \([left, mid)\) 中查找，否则在 \((mid, right]\) 中查找。
重复上述结果，直至 \(left > right\)。
返回 left。
最终算法为：
int leftBound(vector<int> &nums, int target) {
// 搜索区间为 [left, right]
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
} else if (nums[mid] < target) {
// 搜索区间变为 [mid + 1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid - 1]
right = mid - 1;
}
}
// 判断 target 是否存在于 nums 中
// 如果越界，target 肯定不存在，返回 -1
if (left < 0 || left >= nums.size()) {
return -1;
}
return left;
}下面论证当 target 不重复时也不会导致值丢失：
假设在区间 \([left, right]\) 中查找 target，且 target 不重复、恰好处于 mid 位置。
第一次搜索时区间被收缩到 \([left, mid)\)。此区间已经不存在 target，且总比 target 小，因此最终区间会收束到 \([right, right]\) 的位置上。
在最后一轮循环中（也就是 \(left == right == mid - 1\)），由于 \(nums[mid] < target\)，因此会导致 \(left + 1\)。
此时 left 恰好指向 mid，完成循环。
查找右侧边界
查找右侧边界与左侧同理，只是收束方向变为向右收束：
int right_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 最后改成返回 left - 1
if (right < 0 || right >= nums.size()) {
return -1;
}
return right;
}例子
69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的算术平方根 。
由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
分析
现假设给定整数 10，10 的算术平方根为 3.16。通过二分查找可以将题目抽象为：
给定单调非递减数组 \([0, 10]\)，求给定的 \(target = 3.16\)。若 target 存在，返回 target，若 target 不存在，则返回小于 target 的最大值。
根据上文 所提到的可知此题目实际上是在求 target 的右侧边界。和普通二分查找唯一不同的是 target 的计算方式不同。另外还需要注意值溢出的问题：
int Sqrt(int x) {
if (x <= 0) {
return 0;
}
int l = 0;
int r = x;
while (l <= r) {
unsigned long long mid = (r - l) / 2 + l;
long long pow = mid * mid;
if (pow == x) {
l = mid + 1;
} else if (pow > x) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return (r - l) / 2 + l;
}搜索旋转排序数组
对二分查找的一个拓展，需要对数组的有序部分进行判断
数组从某个节点对前后两个部分进行了交换，求一个时间复杂度为 \(O(\log n)\) 的算法[1]
题解：
数组被旋转为了两部分，但是我们依然可以通过判断有序部分使用二分搜索。判断部分分为三个指针：l, mid, target。
如果 arr[l] < arr[mid] 说明 [l,mid] 处于有序部分，这时再进行判断：
如果 target > nums[l] 并且 target < nums[mid] 说明 target 处于有序部分，直接将 r = mid - 1 即可
否则说明 target 不在此部分，将 l = mid + 1 即可
如果 arr[l] > arr[mid] 。因为数组默认是升序排列的，所以这种情况说明 arr[l,mid] 是无序部分。这时再进行判断：
如果 target > arr[mid] 并且 target < arr[l] 说明数据位于 arr[l:] 部分，直接将 l = mid + 1 即可
否则说明数据位于 arr[l,mid]。令 r = mid - 1
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;
if(nums.size() == 1) return nums[0] == target ? 0 : -1;
int l = 0;
int r = nums.size() - 1;
int mid;
while(l < r) {
mid = (l + r) / 2;
if(nums[mid] == target) return mid;
// 数组前半部分和后半部分进行了交换
if(nums[0] <= nums[mid]) {
// 这时说明当前位于前半部分（交换前）
if(nums[0] <= target && target < nums[mid]) r = mid - 1;
else
l = mid + 1;
} else {
if(nums[mid] < target && target <= nums[nums.size() - 1]) l = mid + 1;
else
r = mid - 1;
}
}
return -1;
}
};