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