目录
一. 算法思想
二. 二分搜索的复杂度
三. 二分搜索的使用场景
四. 代码模板
一. 算法思想
-
前提条件:二分搜索算法要求待搜索的数组必须是有序的。通常是升序排列,但也可以是降序排列。
-
基本步骤:
- 初始化:确定搜索范围的起始点和结束点,通常是数组的第一个元素和最后一个元素。
- 循环:在每次循环中,计算搜索范围的中间点。
- 比较:将中间点的值与目标值进行比较:
- 如果中间点的值等于目标值,则搜索成功,返回中间点的索引。
- 如果中间点的值小于目标值,则说明目标值在中间点的右侧,将搜索范围缩小到中间点的右侧。
- 如果中间点的值大于目标值,则说明目标值在中间点的左侧,将搜索范围缩小到中间点的左侧。
- 结束条件:如果搜索范围的起始点大于结束点,则说明目标值不在数组中,搜索失败,返回特定的失败标志(如
-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] 是不是 targetreturn 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;
}
以上便是二分搜索算法模板的核心代码。二分搜索是一种简单而高效的查找算法,尤其适用于需要频繁查找的场景。其应用场景包括但不限于数值查找、字符串查找等,广泛用于计算机科学及相关领域中。理解二分搜索的原理和实现,不仅能够提升编程能力,还能为算法学习打下良好的基础。