跳到主要内容 二分算法:8 道经典题目详解与实战 | 极客日志
C++ 算法
二分算法:8 道经典题目详解与实战 本文通过 8 道经典算法题详细讲解二分查找算法的应用。涵盖标准查找、查找范围、平方根、插入位置、山脉数组峰顶、寻找峰值、旋转数组最小值及缺失数字问题。每道题均提供解题思路、步骤分析及 C++ 代码实现,帮助读者掌握二分法的核心逻辑与边界处理技巧。
1.二分查找
https://leetcode.cn/problems/binary-search/
思路
标准的二分查找。给定一个有序数组和目标值,每次选择数组的中间元素与目标值比较。如果中间元素等于目标值,则返回该索引;若中间元素小于目标值,则在右侧继续搜索;若中间元素大于目标值,则在左侧继续搜索。时间复杂度为 O(log n)。
步骤
初始化:设置 left 和 right 分别为数组的开头和结尾。
二分查找:计算中点 mid。
如果 nums[mid] 等于目标值,返回 mid。
如果 nums[mid] 小于目标值,更新 left = mid + 1。
如果 nums[mid] 大于目标值,更新 right = mid - 1。
终止条件:如果没有找到,返回 -1。
class Solution {
public :
int search (vector<int >& nums, int target) {
int n = nums.size ();
for (int left = 0 , right = n - 1 ; left <= right;) {
int mid = (left + right) / 2 ;
if (nums[mid] < target) left = mid + 1 ;
if (nums[mid] > target) right = mid - 1 ;
if (nums[mid] == target) return mid;
}
;
}
};
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
return
-1
2.在排序数组中查找元素的第一个和最后一个位置
思路 这是经典的'查找范围'问题,可以用两次二分查找解决。第一次找第一个出现位置,第二次找最后一个出现位置。时间复杂度为 O(log n),适合处理排序数组。
步骤 查找第一个位置:使用二分查找,找到目标值的第一个位置。
每次判断 nums[mid] 是否大于等于 target,是则向左移动,否则向右移动。
查找最后一个位置:使用二分查找,找到目标值的最后一个位置。
每次判断 nums[mid] 是否小于等于 target,是则向右移动,否则向左移动。
返回结果:如果找到两个位置,返回它们的范围,否则返回 [-1, -1]。
class Solution {
public :
vector<int > searchRange (vector<int >& nums, int target) {
if (nums.size () == 0 ) return {-1 , -1 };
int n = nums.size ();
int left = 0 , right = n - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] < target) left = mid + 1 ;
if (nums[mid] >= target) right = mid;
}
if (nums[left] != target) return {-1 , -1 };
int begin = left;
right = n - 1 ;
while (left < right) {
int mid = left + (right - left + 1 ) / 2 ;
if (nums[mid] <= target) left = mid;
if (nums[mid] > target) right = mid - 1 ;
}
return {begin, right};
}
};
3.x 的平方根
思路 使用二分查找法求 x 的平方根。定义初始范围为 0,x,每次取中间值 m,计算 m²与 x 的比较。如果 m²小于 x,则移动左边界;如果 m²大于 x,则移动右边界。直至找到平方根或其整数部分。
步骤 初始化:设置 left 为 0,right 为 x。
二分查找:计算中点 mid。
如果 mid * mid 小于 x,说明平方根在右侧,更新 left = mid + 1。
如果 mid * mid 大于 x,说明平方根在左侧,更新 right = mid - 1。
终止条件:当 left 和 right 相遇时,取较小值作为结果的整数部分。
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 if (mid * mid > x) right = mid - 1 ;
}
return left;
}
};
4.搜索插入位置
思路 给定一个有序数组和目标值,要求返回目标值在数组中的插入位置。如果数组中存在目标值,返回其索引;若不存在,返回其应该插入的位置。使用二分查找,找到第一个大于或等于目标值的位置。
步骤 初始化:使用 left 和 right 指针。
二分查找:计算中点 mid。
如果 nums[mid] 大于或等于目标值 target,则将 right 更新为 mid - 1。
否则,将 left 更新为 mid + 1。
终止条件:当 left 和 right 相遇时,left 即为目标值要插入的位置。
class Solution {
public :
int searchInsert (vector<int >& nums, int target) {
int n = nums.size ();
int left = 0 , right = n - 1 ;
while (left <= right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] < target) left = mid + 1 ;
if (nums[mid] > target) right = mid - 1 ;
if (nums[mid] == target) return mid;
}
return left;
}
};
5.山脉数组的峰顶索引
思路 山脉数组是先递增后递减的数组,因此其峰顶就是数组中最大值的位置。可以使用二分查找,类似'寻找峰值'的思路,找到这个峰顶索引。
步骤 初始化:使用 left 和 right 指针,分别指向数组的开头和结尾。
二分查找:计算中点 mid。
如果 nums[mid] 大于 nums[mid + 1],峰顶在左侧,更新 right = mid。
如果 nums[mid] 小于 nums[mid + 1],峰顶在右侧,更新 left = mid + 1。
终止条件:当 left 和 right 相遇时,left 即为峰顶的索引。
class Solution {
public :
int peakIndexInMountainArray (vector<int >& arr) {
int n = arr.size ();
int left = 1 , right = n - 2 ;
while (left < right) {
int mid = left + (right - left + 1 ) / 2 ;
if (arr[mid] < arr[mid - 1 ]) right = mid - 1 ;
else left = mid;
}
return left;
}
};
6.寻找峰值
思路 峰值定义为该元素比相邻元素大。可以使用二分查找的变种。每次选择中点,如果中点比其右侧元素小,则峰值在右侧;如果中点比其右侧元素大,则峰值在左侧。这样逐步缩小搜索范围,直至找到峰值。
步骤 初始化:定义 left 和 right 指针。
二分查找:每次计算中点 mid。
如果 nums[mid] 大于 nums[mid + 1],说明峰值在左侧或就是 mid,更新 right = mid。
如果 nums[mid] 小于 nums[mid + 1],说明峰值在右侧,更新 left = mid + 1。
终止条件:当 left 和 right 相遇时,left 即为峰值所在的位置。
class Solution {
public :
int findPeakElement (vector<int >& nums) {
int left = 0 , right = nums.size () - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] > nums[mid + 1 ]) right = mid;
else left = mid + 1 ;
}
return left;
}
};
7.寻找旋转排序数组中的最小值
思路 旋转排序数组的特点是其包含两个有序的子数组(前一段大于后一段)。最小值通常出现在这两个有序子数组的交界处。可以使用二分查找,比较中点和右端点的值,若中点大于右端点,最小值在右侧;若中点小于右端点,最小值在左侧。
步骤 初始化:定义 left 和 right 指针。
二分查找:每次计算中点 mid。
如果 nums[mid] 大于 nums[right],说明最小值在右侧,更新 left = mid + 1。
否则,最小值在左侧或当前 mid 处,更新 right = mid。
终止条件:当 left 和 right 相遇时,left 即为最小值所在的位置。
class Solution {
public :
int findMin (vector<int >& nums) {
int n = nums.size ();
int left = 0 , right = n - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] > nums[right]) left = mid + 1 ;
else right = mid;
}
return nums[left];
}
};
8.JZ53(2) 缺失的数字
思路 因为数组是排好序的,且数字从 0 到 n-1 连续,可以使用二分查找找到缺失的数字。如果 nums[mid] == mid,说明缺失的数字在右侧;否则在左侧。
class Solution {
public :
int missingNumber (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;
}
return left == records[left] ? left + 1 : left;
}
};
此外这题还可以用 4 种 O(n) 时间复杂度方法去求:第 1 种:直接遍历寻找,第 2 种:哈希,第 3 种:异或,第 4 种:等差求和。