C++算法
二分查找算法经典例题与模板总结
详细讲解了二分查找算法的核心原理，包括二段性判断、时间复杂度分析及数据溢出处理。提供了朴素模板及左右边界查找的通用模板，并结合 LeetCode 经典例题（如搜索插入位置、山脉数组峰顶、旋转排序数组最小值等）进行实战演示。文中包含完整的 C++ 代码实现，帮助读者掌握二分查找在不同场景下的应用技巧。
详细讲解了二分查找算法的核心原理，包括二段性判断、时间复杂度分析及数据溢出处理。提供了朴素模板及左右边界查找的通用模板，并结合 LeetCode 经典例题（如搜索插入位置、山脉数组峰顶、旋转排序数组最小值等）进行实战演示。文中包含完整的 C++ 代码实现，帮助读者掌握二分查找在不同场景下的应用技巧。
二分算法的满足条件是数组有序，其实并不严谨，实际上是要具有二段性，即通过有一个数能将数组分为两部分，一次比较能筛选掉一部分。
循环结束条件：
left > right，因为每个区间内的数都是未知的，即使最后 left 和 right 相等还是要跟目标值比较一次，来证明一个数是否存在。
时间复杂度：
O(logN) 和 O(N) 的效率差距很大，在 int 范围内，O(N) 最多要比较执行 4*10^9 次，而 O(logN) 最多只要 32 次。
数据溢出问题：
(left + right) / 2：在大多数情况下是安全的，但如果 left 和 right 的和超过了该类型能表示的最大值，直接相加可能会导致整数溢出。 left + (right - left) / 2 可以避免这个问题，利用起始值 + 偏移值可以有效避免两数相加超出范围，结果相同。
至于 left + (right - left + 1) / 2 和 (left + right + 1) / 2 要不要加 1 的问题，在数组数量为奇数时结果相同。不同在于数量为偶数时中间值有两个数，不加 1 和加 1 计算结果一个在左中间值一个在右中间值，并不影响最终结果。
该模板为最朴素的二分查找模板，适用范围一般限制较多，后续会总结左右边界的判断模板，为万能模板，适用范围更广。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else if (nums[mid] == target) return mid;
}
return -1;
}
};
非递减顺序排列就是递增序列或不变。
由于该题给定数组要么是递增要么不变，可以用一个值划分两个区间，所以具有二段性，符合使用二分算法的条件。
与上题总结的朴素模板相比，该题的判断条件要发生变化。根据举例找出一般规律：
循环条件为 left < right：数组内元素总共三种情况，存在左端点、元素全部小于目标值、全部大于目标值，当 left == right 时就是最终结果，无需判断。如果判断当数组内元素全部小于目标值时 left = mid+1 刚好结束循环，但若元素大于等于目标值时 right = mid 会陷入死循环。
1 式在 x < t 时 left = mid+1 移动到 right 处结束循环，当 x >= t 时 right = mid 移动到 left 处结束循环。 2 式在 x < t 时 left = mid+1 移动到 right+1 处结束循环，但 x >= t 时 right = mid 位置不变会陷入死循环。
同理通过分析例子得出一般规律：
与寻找左端点相同，都是 left < right。
分析过程与求左端点思路相同，无非是当元素为偶数个时中间点有两个，取左还是右，当其中一个在 x <= t 条件下 left == mid 下标都未发生变化因此会陷入死循环，不再赘述。
画星部分不用特意去记，根据题意分析二段性就可以得出，求中间值的方法可以这么想，当求左端点时，当数组元素为偶数个数时中间值有两个，mid 落在左边那个，对应的计算方法就不要 +1，反之求右端点时 mid 落在中间值右边那个，计算方法要 +1，循环判断条件都相同。 更万能的记忆的方法，当 if 条件语句中出现了减法，那么中间值的计算就要 +1。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 判断数组为空的情况
if (nums.size() == 0) return {-1, -1};
// 判断数组是否具有 target 元素
int n = 0;
for (auto e : nums)
if (e == target) n++;
if (n == 0) return {-1, -1};
// 查找左端点
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
// 查找右端点
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l + 1) / 2;
if (nums[m] <= target) l = m;
else r = m - 1;
}
return {left, r}; // 最后写左右都可以，它们最终会相遇
}
};
依次枚举所有数的平方，枚举区间为整个数组不需要额外判断，当等于目标值时直接返回，大于时说明前一个为结果。需注意由于是相乘，有可能超过 int 的最大值，应该使用 long long 类型。
class Solution {
public:
int mySqrt(int x) {
// 由于两个较大的数相乘可能会超过 int 最大范围
// 因此用 long long
long long i = 0;
for (i = 0; i <= x; i++) {
// 如果两个数相乘正好等于 x，直接返回 i
if (i * i == x) return i;
// 如果第一次出现两个数相乘大于 x，说明结果是前一个数
if (i * i > x) return i - 1;
}
// 为了处理 oj 题需要控制所有路径都有返回值
return -1;
}
};
可以根据目标值来划分区间，具有二段性。[0, ret] 之间的元素，平方之后都是小于等于 x 的，ret 可能为目标值，令 left = ret；[ret + 1, x] 之间的元素，平方之后都是大于 x 的，令 right = ret-1。 如果按小于 x 和大于等于 x 的区间来划分同理，分别令 left = mid+1 和 right = mid 即可。
class Solution {
public:
int mySqrt(int x) {
if (x < 1) return 0; // 处理边界情况
int left = 1, right = x;
while (left < right) {
long long mid = left + (right - left + 1) / 2; // 防溢出
if (mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}
};
设插入位置为 ret，根据题意分析二段性可划分为小于目标值 t 和大于等于 t 的区域，左右指针的移动情况如下，当 mid 落在 [left, ret-1] 区域时由于全部小于 t，令 left = mid+1；当 mid 落在 [ret, right] 中时由于 ret 可能为目标值所以令 right = mid。
class Solution {
public:
int searchInsert(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 right = mid;
}
// 判断目标值大于数组中最大元素的情况，根据题意要返回下一位索引
if (target > nums[right]) return right + 1;
return left; // 由于左右指针已经相遇，返回谁都可以
}
};
峰顶的特点：比两侧的元素都要大。因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
// 遍历数组内每一个元素，直到找到峰顶
for (int i = 1; i < n - 1; i++)
// 峰顶满足的条件
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) return i;
// 为了处理 oj 需要控制所有路径都有返回值
return -1;
}
};
虽然该题数组不有序，但具有二段性，山峰左右两边都小于山峰值，中间位置 mid 可以分为以下两种种情况：
峰值 mid 一定得放到左边区间中，因为是和前一个元素作比较，左区间中的最后一个元素可能位峰值，若放到右边区间中更新索引时峰值可能会被跳过，mid 的计算要 +1。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1, right = arr.size() - 2;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (arr[mid] > arr[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
};
此时将峰值放到右边区间，右边区间的第一个元素可能为峰值，更新时 right = mid，left = mid+1，此时 mid 的计算不 +1。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1, right = arr.size() - 2;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid + 1] > arr[mid]) left = mid + 1;
else right = mid;
}
return left;
}
};
由题意得数组升序，旋转后具有两段性。 旋转后的数据分为这样两段，C 点即为所求最小值。我们以 D 点作为划分值。 当 mid 落在 AB 区间时不满足，left = mid+1 要跳出该区间；落在 CD 区间时 mid <= 最小值，为了缩小搜寻范围令 right = mid。
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size() - 1;
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[n]) left = mid + 1;
if (nums[mid] <= nums[n]) right = mid;
}
return nums[right];
}
};
二分查找
由题意得数组递增且有序，中间会少一个数，这个数就可以把数组划分为两个区间。 前区间元素值对应索引，后区间元素对应索引 +1，我们要求的就是后区间的第一个元素。
细节问题：
若数组未被划分为两个区间，每个元素都等于其索引，那缺失值超出数组索引有效范围，返回最后索引 +1。
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left = 0, right = records.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (records[mid] == mid) left = mid + 1;
else right = mid;
}
// 完全连续的特殊情况判断
if (records[right] == right) return right + 1;
else return right;
}
};
除此之外还可以尝试：
- 哈希表
- 直接遍历找结果
- 位运算
- 数学 (高斯求和公式) 这些方法的时间复杂度都为 O(n)，不如二分。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online