二分搜索算法
目录
一. 算法思想
-
前提条件:二分搜索算法要求待搜索的数组必须是有序的。通常是升序排列,但也可以是降序排列。
-
基本步骤:
- 初始化:确定搜索范围的起始点和结束点,通常是数组的第一个元素和最后一个元素。
- 循环:在每次循环中,计算搜索范围的中间点。
- 比较:将中间点的值与目标值进行比较:
- 如果中间点的值等于目标值,则搜索成功,返回中间点的索引。
- 如果中间点的值小于目标值,则说明目标值在中间点的右侧,将搜索范围缩小到中间点的右侧。
- 如果中间点的值大于目标值,则说明目标值在中间点的左侧,将搜索范围缩小到中间点的左侧。
- 结束条件:如果搜索范围的起始点大于结束点,则说明目标值不在数组中,搜索失败,返回特定的失败标志(如
-1
)。
二. 二分搜索的复杂度
- 时间复杂度:
O(log n)
,其中n
是数组的长度。每次查找都将问题的规模减半,因此执行的步骤数量与输入规模的对数成正比。 - 空间复杂度:
O(1)
(如果是非递归实现)或者O(log n)
(如果是递归实现,主要是由于递归调用栈的占用)。
三. 二分搜索的使用场景
二分搜索不仅可以用于查找单个元素,还可以进行一些变种操作,例如:
- 查找第一个出现的位置:在数组中查找目标值第一次出现的索引。
- 查找最后一个出现的位置:在数组中查找目标值最后一次出现的索引。
- 查找大于等于目标值的最小值:可以用来解决一些与插入位置相关的问题。
- 查找小于等于目标值的最大值。
四. 代码模板
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 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) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
// 左边界
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 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) {
// 别返回,锁定左侧边界
right = mid - 1;
}
}
// 判断 target 是否存在于 nums 中
if (left < 0 || left >= nums.length) {
return -1;
}
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;
}
// 右边界
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 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;
}
}
// 由于 while 的结束条件是 right == left - 1,且现在在求右边界
// 所以用 right 替代 left - 1 较为好记一些
if (right < 0 || right >= nums.length) {
return -1;
}
return nums[right] == target ? right : -1;
}
以上便是二分搜索算法模板的核心代码。二分搜索是一种简单而高效的查找算法,尤其适用于需要频繁查找的场景。其应用场景包括但不限于数值查找、字符串查找等,广泛用于计算机科学及相关领域中。理解二分搜索的原理和实现,不仅能够提升编程能力,还能为算法学习打下良好的基础。
原文地址:https://blog.csdn.net/m0_62965917/article/details/142727030
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!