个人免费网站建站排名,岫岩网站建设,php企业cms,wordpress禁止图片点击文章目录
须知 #x1f4ac; 欢迎讨论#xff1a;如果你在学习过程中有任何问题或想法#xff0c;欢迎在评论区留言#xff0c;我们一起交流学习。你的支持是我继续创作的动力#xff01; #x1f44d; 点赞、收藏与分享#xff1a;觉得这篇文章对你有帮助吗#xff1…文章目录
须知 欢迎讨论如果你在学习过程中有任何问题或想法欢迎在评论区留言我们一起交流学习。你的支持是我继续创作的动力 点赞、收藏与分享觉得这篇文章对你有帮助吗别忘了点赞、收藏并分享给更多的小伙伴哦你们的支持是我不断进步的动力 分享给更多人如果你觉得这篇文章对你有帮助欢迎分享给更多对C算法感兴趣的朋友让我们一起进步 1. C 二分查找算法 详解
1.1 二分查找算法的重要性
二分查找Binary Search是一种经典的算法广泛应用于计算机科学中尤其在处理有序数据时。其重要性体现在以下几个方面 高效性 时间复杂度为 O(logn)相比于线性搜索的 O(n)在大规模数据集上性能提升显著。特别适用于查找频繁的场景如搜索引擎、数据库索引等。 普适性 不仅可以应用于查找问题还能扩展到解决复杂问题如求解特定函数值、二分答案法、优化问题的解空间收缩等。 简洁性 算法简单易实现逻辑清晰适合初学者掌握编程和算法的基本思想。二分查找思想可以扩展到多种变体如上下界查找、最优解逼近等。 应用广泛 排序数组中的查找问题。数学问题求解如平方根、最大值最小化等。各种问题优化如动态规划中的状态转移点查找。
1.2 什么是二分查找算法
二分查找是一种在 有序数组 中查找目标值的算法。通过每次将查找范围缩小一半逐步逼近目标值的位置。
定义核心
二分查找的目标是利用有序性将搜索范围逐步减少到最小。通过比较中间值与目标值决定在左右半区继续搜索。 1.3 核心思想
核心思想可以概括为“分而治之” 缩小搜索范围 每次比较目标值和中间值根据有序性决定继续查找左半部分还是右半部分排除另一半不可能的区域。 递归或迭代 通过递归或迭代实现搜索范围不断缩小。最终在可能的区间中找到目标值或者确认目标值不存在。 有序性约束 二分查找仅适用于有序数组或可以逻辑上排序的空间是其适用性的前提。 二分查找的基本步骤 初始化范围 定义左右边界 left 和 right初始为数组的起点和终点。 计算中点 根据公式 mid left (right - left) / 2 计算中间索引避免溢出。 判断目标值 如果目标值等于中点值直接返回。如果目标值小于中点值缩小右边界 right mid - 1。如果目标值大于中点值缩小左边界 left mid 1。 退出条件 当 left right 时说明目标值不存在结束搜索。 1.4 二分查找的典型应用
数组查找 在排序数组中快速查找目标值。上/下界查找 查找目标值的第一个或最后一个出现位置。函数值逼近 在某范围内寻找特定条件满足的最优值。复杂问题解空间缩减 如动态规划中的优化问题状态转移优化。
2. 二分查找算法模版
2.1 标准二分查找模板 用于在 有序数组 中查找某个目标值。 int binarySearch(vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) { // 搜索区间为 [left, right]int mid left (right - left) / 2; // 避免溢出if (nums[mid] target) {return mid; // 找到目标值返回索引} else if (nums[mid] target) {left mid 1; // 缩小到右半部分} else {right mid - 1; // 缩小到左半部分}}return -1; // 未找到目标值
}
特点
适用场景查找目标值返回其索引。退出条件当 left right 时说明目标值不存在。时间复杂度O(logn)。
2.2 查找左侧边界的二分查找 查找目标值的 最左位置。 int lowerBound(vectorint nums, int target) {int left 0, right nums.size();while (left right) { // 搜索区间为 [left, right)int mid left (right - left) / 2;if (nums[mid] target) {left mid 1; // 缩小到右半部分} else {right mid; // 缩小到左半部分}}return left; // 返回左边界
}如果目标值存在返回其左边界索引。如果目标值不存在返回插入位置。适用场景查找目标值的第一个出现位置或者获取目标值插入有序数组的位置。
2.3 查找右侧边界的二分查找 查找目标值的 最右位置。 int upperBound(vectorint nums, int target) {int left 0, right nums.size();while (left right) { // 搜索区间为 [left, right)int mid left (right - left) / 2;if (nums[mid] target) {left mid 1; // 缩小到右半部分} else {right mid; // 缩小到左半部分}}return left - 1; // 返回右边界索引
}特点
如果目标值存在返回其右边界索引。如果目标值不存在返回小于目标值的最大元素位置。
2.4 查找目标值范围二分查找综合模板 同时查找目标值的左、右边界适用于数组中目标值重复出现。 vectorint searchRange(vectorint nums, int target) {int left 0, right nums.size() - 1;// 查找左边界int start -1, end -1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {right mid - 1;} else {left mid 1;}}if (left nums.size() nums[left] target) {start left;} else {return {-1, -1}; // 目标值不存在}// 查找右边界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 - 1;}}end right;return {start, end};
}特点
适用于查找区间 [start, end]。如果目标值不存在返回 {-1, -1}。 2.5 二分答案法模板 适用于需要在范围内找到满足某种条件的最优解。 int binaryAnswer(int low, int high, functionbool(int) condition) {while (low high) {int mid low (high - low) / 2;if (condition(mid)) {high mid; // 满足条件收缩右边界} else {low mid 1; // 不满足条件收缩左边界}}return low; // 返回最小满足条件的值
}特点
通过逻辑条件函数 condition(mid) 判断是否满足目标。常用于优化问题如最大值最小化、最小值最大化等。
2.6 常见边界问题注意点 搜索区间是否包含 right [left, right] 区间通常用于包含上下界查找。[left, right) 区间通常用于统一逻辑更适合下界查找。 mid 计算防止溢出 使用 mid left (right - left) / 2。 退出条件的灵活性 对于不同区间范围和边界需求while (left right) 和 while (left right) 需区别对待。
2.7 总结
标准模板快速定位目标值。变体模板查找上下界或目标值范围。扩展模板适用于更复杂的优化问题。 掌握不同场景下的二分查找模板能够快速高效解决查找与优化问题。
3. 题目1二分查找
题目链接704. 二分查找 - 力扣LeetCode
题目描述 3.1 算法思路 核心思想 利用 二分查找算法在有序数组中查找目标值。每次通过比较中间值与目标值的大小缩小搜索范围直到找到目标值或搜索范围为空。
3.1.1 具体步骤 初始化搜索范围 左边界 left 初始化为数组起点 0。右边界 right 初始化为数组终点 nums.size() - 1。 二分循环查找 当 left right 时 计算中间索引 mid left (right - left) / 2避免整数溢出。如果 nums[mid] target直接返回索引 mid。如果 nums[mid] target目标值在右半部分将 left 更新为 mid 1。如果 nums[mid] target目标值在左半部分将 right 更新为 mid - 1。 返回结果 如果退出循环仍未找到目标值返回 -1。
3.2 示例代码
class Solution {
public:int search(vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) { // 搜索区间为 [left, right]int mid left (right - left) / 2; // 计算中点防止溢出if (nums[mid] target) {return mid; // 找到目标值返回索引} else if (nums[mid] target) {left mid 1; // 目标值在右半部分} else {right mid - 1; // 目标值在左半部分}}return -1; // 未找到目标值}
};3.2.1 示例解析
示例 1
输入nums [-1, 0, 3, 5, 9, 12], target 9 输出4
执行过程
初始化left 0, right 5。第 1 步mid (0 5) / 2 2nums[mid] 3 9更新 left 3。第 2 步mid (3 5) / 2 4nums[mid] 9 9返回索引 4。
3.3 时间与空间复杂度
3.3.1 时间复杂度
O(log n) 每次迭代将搜索范围缩小一半因此时间复杂度是对数级别。
3.3.2 空间复杂度
O(1) 只使用了常数空间无额外数组或递归调用栈。 边界条件分析 空数组 如果 nums 为空right nums.size() - 1 -1循环直接跳过返回 -1。目标值不在数组中 如果目标值不在数组中循环最终会将 left right返回 -1。目标值在边界 如果目标值是数组中的最小值或最大值算法可以正确返回索引。
3.4 补充可看可不看 暴力解法 3.4.1 暴力解法思路
暴力解法的核心是直接遍历数组 nums 中的每一个元素逐一与目标值 target 进行比较直到找到目标值或遍历结束。
3.4.2 具体步骤
遍历数组 从左到右逐一访问数组中的每一个元素。比较当前元素与目标值 如果当前元素等于目标值返回当前索引。返回结果 如果遍历结束仍未找到目标值返回 -1 表示目标值不存在。
3.4.3 示例代码
class Solution {
public:int search(vectorint nums, int target) {for (int i 0; i nums.size(); i) {if (nums[i] target) {return i; // 找到目标值返回索引}}return -1; // 未找到目标值}
};3.4.4 时间与空间复杂度
时间复杂度
最坏情况 当目标值位于数组末尾或者不存在时需要遍历整个数组时间复杂度为 O(n)其中 n 是数组长度。最佳情况 当目标值是数组中的第一个元素时时间复杂度为 O(1)。平均情况 O(n)因为没有利用数组的有序性。
空间复杂度
O(1) 只使用了常量级别的额外空间没有引入新的数据结构。 暴力解法的优缺点 优点
简单直接 实现简单逻辑清晰。对初学者友好无需理解复杂算法。通用性强 无需假设数组是有序的可直接用于任意数组。
缺点
效率低下 对于大规模数组时间复杂度 O(n) 远高于二分查找的 O(logn)。未利用数组的有序性性能不佳。不符合题目要求 题目中数组是有序的暴力解法没有利用这一特性。
3.4.5 与二分查找对比 3.4.6 总结
暴力解法逻辑简单适合入门或小规模数据场景。二分查找则充分利用了有序数组的特性更适合大规模查找性能更优。
3.5 总结
算法思路利用有序数组的性质每次缩小搜索范围逐步找到目标值或确定其不存在。时间复杂度O(logn)适合大规模数据的查找。边界处理代码能够正确处理空数组、目标值不在数组中、目标值在边界等特殊情况。 4. 题目2在排序数组中查找元素的第一个和最后一个位置
题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
题目描述 4.1 算法思路
这道题的核心是利用 二分查找 在排序数组中分别找到目标值的左右边界。
1. 核心思想 找到左边界第一个等于 target 的元素的索引。 找到右边界最后一个等于 target 的元素的索引。 如果找不到目标值直接返回 [-1, -1]。
2. 使用两次二分查找 查找左边界定位目标值在数组中的最左位置。 查找右边界定位目标值在数组中的最右位置。
4.2 示例代码 class Solution {
public:vectorint searchRange(vectorint nums, int target) {// 查找左边界int left 0, right nums.size() - 1;int leftIndex -1, rightIndex -1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {right mid - 1;} else {left mid 1;}}if (left nums.size() nums[left] target) {leftIndex left;} else {return {-1, -1}; // 如果左边界不存在直接返回}// 查找右边界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 - 1;}}if (right 0 nums[right] target) {rightIndex right;}return {leftIndex, rightIndex};}
};详细步骤 4.2.1 查找左边界
初始化 left 0right nums.size() - 1。在循环中通过二分查找找到第一个大于或等于 target 的位置 如果 nums[mid] target则目标值在右侧调整 left mid 1。如果 nums[mid] target则调整 right mid - 1。最后检查 nums[left] 是否等于 target如果相等返回 left否则返回 -1。
4.2.2 查找右边界
初始化 left 0right nums.size() - 1。在循环中通过二分查找找到最后一个小于或等于 target 的位置 如果 nums[mid] target则目标值在左侧调整 right mid - 1。如果 nums[mid] target则调整 left mid 1。最后检查 nums[right] 是否等于 target如果相等返回 right否则返回 -1。 示例解析 示例 1 输入nums [5,7,7,8,8,10], target 8 输出[3,4] 执行过程
查找左边界 初始范围left 0, right 5。第一次mid 2nums[2] 7 8更新 left 3。第二次mid 4nums[4] 8更新 right 3。第三次mid 3nums[3] 8更新 right 2。左边界为 3。查找右边界 初始范围left 0, right 5。第一次mid 2nums[2] 7 8更新 left 3。第二次mid 4nums[4] 8更新 left 5。第三次mid 5nums[5] 10 8更新 right 4。右边界为 4。
输出 [3,4] 4.3 时间与空间复杂度
4.3.1 时间复杂度
每次二分查找的时间复杂度为 O(logn)。两次二分查找总时间复杂度为 O(2⋅logn)O(logn)。
4.3.2 空间复杂度
只使用常量级额外空间空间复杂度为 O(1)。
4.4 总结 算法特点 使用二分查找分别找到左边界和右边界。时间复杂度 O(logn)适合大规模数据。空间复杂度 O(1)仅使用常量级变量。 代码结构清晰 两次独立的二分查找易于理解和调试。 特殊情况处理 数组为空或目标值不存在时返回 [-1, -1]。 5. 题目3搜索插入位置
题目链接35. 搜索插入位置 - 力扣LeetCode
题目描述 5.1 算法思路
核心思想二分查找
由于数组是升序排序的因此可以使用二分查找在 O(logn) 时间复杂度内找到目标值的插入位置。 5.2 示例代码
class Solution
{
public:int searchInsert(vectorint nums, int target) {// 定义左右边界int left 0, right nums.size() - 1;// 特殊情况如果目标值大于数组中所有元素则插入到数组末尾if (nums[right] target) return right 1;// 二分查找while (left right) {// 计算中间位置避免溢出int mid left (right - left) / 2;// 如果中间值小于目标值目标值在右半部分if (nums[mid] target) left mid 1; // 调整左边界else // 如果中间值大于等于目标值目标值可能在左半部分right mid; // 调整右边界}// 最终 left right返回插入位置return left;}
};5.2.1 注释内容说明 特殊处理nums[right] target 如果目标值大于数组中的最大值则目标值一定插入到数组末尾。为了提高效率先检查这一特殊情况。 二分查找核心 使用 while (left right) 循环通过不断缩小区间找到目标值或插入位置。使用 mid left (right - left) / 2 计算中点避免 left right 的溢出问题。 区间调整逻辑 当 nums[mid] target 时说明目标值在右半部分更新左边界 left mid 1。否则目标值在左半部分或 nums[mid] target更新右边界 right mid。 最终返回 循环退出时left right此时 left 即为目标值所在位置或插入位置。
5.3 时间与空间复杂度
时间复杂度O(logn) 二分查找每次将搜索范围缩小一半复杂度是对数级。空间复杂度O(1) 无额外空间开销。
5.4 补充可看可不看
5.4.1 暴力解法
暴力解法的核心是 直接遍历数组
遍历数组中的每个元素与目标值 target 进行比较。如果找到一个元素大于或等于目标值返回该元素的索引。如果遍历结束仍未找到说明目标值比数组中所有元素都大返回数组的长度。
这种方法时间复杂度是 O(n)适合小规模数组。
5.4.2 示例代码
class Solution
{
public:int searchInsert(vectorint nums, int target) {for (int i 0; i nums.size(); i) {// 如果找到第一个大于或等于目标值的位置返回索引if (nums[i] target) return i;}// 如果目标值比所有元素都大返回数组长度return nums.size();}
};5.4.3 示例解析
示例 1
输入nums [1, 3, 5, 6], target 5 输出2
执行过程
遍历到 nums[0] 11 5继续。遍历到 nums[1] 33 5继续。遍历到 nums[2] 55 5返回索引 2。 5.4.4 时间与空间复杂度
时间复杂度
最坏情况目标值比数组所有元素都大需要遍历整个数组时间复杂度为 O(n)。最佳情况目标值小于数组第一个元素直接返回索引 0时间复杂度为 O(1)。
空间复杂度
O(1)不需要额外的存储空间。 优缺点分析 优点 简单直接易于实现。 适合小规模数组的情况。
缺点
时间复杂度较高不适合大规模数组。没有利用数组的有序性效率较低。
5.5 总结 关键点 明确目标值可能是数组中的一个元素也可能是插入的位置。使用二分查找高效缩小范围。返回 left 即为插入位置。 扩展场景 如果需要返回目标值的插入位置同时要求区分左、右边界可以进一步扩展这段代码逻辑。
6. 题目4x的平方根
题目链接69. x 的平方根 - 力扣LeetCode
题目描述 6.1 算法思路
6.1.1 问题本质
我们要找到满足以下条件的最大整数 y
y2≤x(y1)2x
6.1.2 核心思想
利用 二分查找 来寻找平方根 二分查找的搜索区间是 [1, x]因为 x\sqrt{x}x 最大不会超过 x 本身。 每次取中点 mid计算 mid2 与 x 比较 如果 mid2 ≤ x说明平方根在右侧更新 left mid。如果 mid2 x说明平方根在左侧更新 right mid - 1。 循环退出时left 指向平方根的整数部分。
6.2 示例代码
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) right mid - 1; // 排除右半部分else left mid; // 更新左边界保留 mid}return left; // 最终返回平方根的整数部分}
};版本2
class Solution
{
public:int mySqrt(int x) {if (x 0) return 0; // 直接处理特殊情况int left 1, right x;while (left right) // 使用闭区间 [left, right]{int mid left (right - left) / 2;if (mid x / mid) // 避免溢出left mid 1; // 更新左边界elseright mid - 1; // 更新右边界}return right; // 返回右边界即平方根整数部分}
};6.2.1 关键点解析 初始化区间 区间为 [1, x]因为平方根不会小于 1 且不会大于 x对于 x≥1。 中点计算 使用 mid left (right - left 1) / 2 来计算中点避免直接加法可能导致的溢出。向上取整 的目的是保证当区间只有两个元素时选择靠右的中点从而能够正确排除区间。 更新区间 如果 mid2xright mid - 1排除当前的 mid 和右侧部分。如果 mid2xleft mid保留当前的 mid。 返回值 循环退出条件是 left right此时 left 即为平方根的整数部分。
6.3 补充可看可不看 暴力解法 6.3.1 示例代码
class Solution
{
public:int mySqrt(int x) {if (x 0) return 0; // 特殊情况处理int y 0;while ((long long)y * y x) // 防止溢出{y;}return y - 1; // 返回满足条件的最大整数}
};6.3.2 时间与空间复杂度
时间复杂度 最坏情况如果 x 很大如 x 10^9暴力解法需要从 0 遍历到 x\sqrt{x}因此时间复杂度为 O(x\sqrt{x})。 最佳情况如果 x0 或 x1复杂度为 O(1)。
空间复杂度
O(1)仅使用了常量级别的变量 y 和计算不需要额外空间。 优缺点分析 优点 简单直观 不依赖复杂的算法逻辑直接枚举。 易于理解和实现。 无特殊处理 不需要处理二分查找的边界条件也无需考虑浮点数计算误差。
缺点 效率低下 时间复杂度为 O(\sqrt{x})对于较大的 x如 10^9效率明显低于二分查找法的 O(logx)。 对大数的适用性差 如果没有使用 long long 类型会因为 y2 的溢出问题导致错误结果。 6.4 时间与空间复杂度
6.4.1 时间复杂度
二分查找的时间复杂度是 O(logx)因为每次迭代将搜索区间缩小一半。
6.4.2 空间复杂度
只使用了常量额外空间空间复杂度是 O(1)。
6.5 对比 6.6 总结 算法思想 二分查找用于在区间 [1, x] 中寻找满足 y2≤x 的最大整数 y。 复杂度 时间复杂度 O(logx)空间复杂度 O(1)。 注意事项 需要特别处理 x 0 和 x 1 等特殊情况。通过 mid x / mid 避免溢出问题。
6.7 最后 通过上述例题分析可以看出二分查找的核心用途是 快速缩小搜索范围解决有序数据、边界条件和单调问题等场景。在实际问题中熟练掌握二分查找模板和变体是解决高效算法问题的关键。 路虽远行则将至事虽难做则必成 亲爱的读者们下一篇文章再会
