简要介绍
二分算法是算法题目中常见的一种优化算法,很好地体现了分治的思想。该算法不仅在算法题目中屡见不鲜,在实际工程中也十分热门,例如数据库索引、文件系统以及游戏 AI 的路径规划等。常见的二分算法类型包括二分答案、二分区间和二分浮点数。
二分查找算法的基本思想及应用场景,涵盖二分答案、二分区间和二分浮点数三种类型。通过四个 LeetCode 经典例题(二分查找、在排序数组中查找元素的第一个和最后一个位置、搜索插入位置、x 的平方根),详细讲解了题目分析、实现思路及 C++ 代码实现。重点阐述了左右边界查找、取整技巧及时间复杂度优化至 O(log n) 的方法,适合算法初学者入门。

二分算法是算法题目中常见的一种优化算法,很好地体现了分治的思想。该算法不仅在算法题目中屡见不鲜,在实际工程中也十分热门,例如数据库索引、文件系统以及游戏 AI 的路径规划等。常见的二分算法类型包括二分答案、二分区间和二分浮点数。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 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
二分答案:在有单调性的区间中找值,通过二分思想调整查找范围。
二分区间:搜索一个区间而非单个值,常应用于在区间内查找某一个解的情况。
二分浮点数:处理方式略有不同,但核心思想类似二分答案。
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,写一个函数搜索 nums 中的 target。如果 target 存在返回下标,否则返回 -1。必须编写一个具有 O(log n) 时间复杂度的算法。
示例 1:
输入:nums = [-1,0,3,5,9,12], target = 9
输出:4
解释:9 出现在 nums 中并且下标为 4
示例 2:
输入:nums = [-1,0,3,5,9,12], target = 2
输出:-1
解释:2 不存在 nums 中因此返回 -1
提示:
nums 中的所有元素是不重复的。n 将在 [1, 10000] 之间。nums 的每个元素都将在 [-9999, 9999] 之间。这是一道经典的二分答案题目,核心思想就是二分。
定义两个指针,左指针 left 和右指针 right,分别指向数组的左右端点,计算中间点 mid。讨论三种情况:
nums[mid] == target:说明找到了,直接返回。nums[mid] > target:说明区间 [mid, right] 的值都大于 target,舍弃该区间,在左边 [left, mid - 1] 继续查找,即 right = mid - 1。nums[mid] < target:说明区间 [left, mid] 的值都小于 target,舍弃该区间,在右边 [mid + 1, right] 继续查找,即 left = mid + 1。以上操作在 while(left <= right) 条件下进行,跳出循环说明未找到。
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
};
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 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 <= 10^5-10^9 <= nums[i] <= 10^9nums 是一个非递减数组-10^9 <= target <= 10^9这是二分区间的经典例题。基础二分模板保留特定左或右下标的方式可能找不到等于 target 的值,这里需要确保找到的是等于 target 的边界。
分别找到左边界和右边界。
找左边界:
明确区间特点:左区间 [left, k - 1] 小于 target,右区间 [k, right] 大于等于 target。
mid 在 [left, k - 1] 时,nums[mid] < target,舍弃 [left, mid],更新 left = mid + 1。mid 在 [k, right] 时,nums[mid] >= target,不能舍弃 k,舍弃 [left + 1, right],更新 right = mid。
注意:此处需向下取整,避免死循环。找右边界:
明确区间特点:左区间 [left, k] 小于等于 target,右区间 [k + 1, right] 大于 target。
mid 在 [left, k] 时,nums[mid] <= target,不能舍弃 mid,舍弃 [left, mid - 1],更新 left = mid。mid 在 [k + 1, right] 时,nums[mid] > target,舍弃 [mid, right],更新 right = mid - 1。
注意:此处需向上取整。class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
if (n == 0) return {-1, -1};
// 找左边界
int left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
int Left = 0;
if (nums[left] != target) return {-1, -1};
else Left = left;
// 找右边界
left = 0; right = n - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) left = mid;
else right = mid - 1;
}
return {Left, left};
}
};
这里给一个取整的小技巧:while 循环里有
-1,取整就要+1;反之则没有+1。
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入:nums = [1,3,5,6], target = 5
输出:2
示例 2:
输入:nums = [1,3,5,6], target = 2
输出:1
示例 3:
输入:nums = [1,3,5,6], target = 7
输出:4
提示:
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums 为无重复元素的升序排列数组-10^4 <= target <= 10^4该题目可转换为找出大于等于目标值的最左端,复用之前写的代码。
使用二分基础模板,标记大于等于目标值的下标。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int ret = -1;
int left = 0, right = nums.size() - 1;
if (nums[nums.size() - 1] < target) return nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
};
class Solution {
public:
int searchInsert(vector<int>& a, int value) {
int L = 0;
int R = a.size() - 1;
if (a[a.size() - 1] < value) return a.size();
int index = -1;
while (L <= R) {
int mid = L + ((R - L + 1) >> 1);
if (a[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
};
给你一个非负整数 x,计算并返回 x 的算术平方根。由于返回类型是整数,结果只保留整数部分,小数部分将被舍去。不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 2^31 - 1实际求的是小于等于根号 x 的最大值,可复用第二题或第三题的代码二。
条件改变,基本思路一致。
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x;
if (x < 1) return 0;
while (left < right) {
long long mid = left + (right - left + 1) / 2;
if (mid * mid <= x) left = mid;
else right = mid - 1;
}
return left;
}
};
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x;
if (x < 1) return 0;
int index = -1;
while (left <= right) {
long long mid = left + (right - left + 1) / 2;
if (mid * mid <= x) {
index = mid;
left = mid + 1;
} else right = mid - 1;
}
return index;
}
};