递归算法之二分搜索（Binary Search）详细解读

二分搜索（Binary Search）是一种高效的查找算法，适用于有序数组或列表。它通过逐步缩小查找范围来快速定位目标元素，时间复杂度为 O(log⁡n)，远比线性搜索的 O(n) 要快。二分搜索的基本思想是每次将查找范围缩小一半，因此特别适合于处理大规模数据。

1. 二分搜索的基本思想

给定一个递增排序的数组，我们希望在其中查找某个目标元素。二分搜索的过程是：

取数组的中间元素，并与目标元素比较。
如果中间元素等于目标元素，则查找成功。
如果中间元素小于目标元素，则在右半部分继续查找。
如果中间元素大于目标元素，则在左半部分继续查找。
重复这个过程，直到找到目标元素或查找范围为空。

2. 二分搜索的步骤

假设我们有一个排序数组 arr，目标元素为 target。其查找过程可以描述如下：

初始化两个指针：low 指向数组的起始位置，high 指向数组的末尾位置。
计算中间索引 mid = low + (high - low) / 2。
比较 arr[mid] 与 target：
- 如果 arr[mid] == target，则找到目标，返回 mid。
- 如果 arr[mid] < target，则 target 只可能在右半部分，调整 low = mid + 1。
- 如果 arr[mid] > target，则 target 只可能在左半部分，调整 high = mid - 1。
当 low > high 时，表示数组中没有目标元素，查找失败。

3. 二分搜索的实现

3.1 迭代实现

public class BinarySearch {// 二分查找的迭代实现public static int binarySearch(int[] arr, int target) {int low = 0;int high = arr.length - 1;while (low <= high) {int mid = low + (high - low) / 2;  // 避免整数溢出if (arr[mid] == target) {return mid;  // 找到目标，返回索引} else if (arr[mid] < target) {low = mid + 1;  // 在右半部分查找} else {high = mid - 1;  // 在左半部分查找}}return -1;  // 没有找到目标元素}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13};int target = 7;int result = binarySearch(arr, target);if (result != -1) {System.out.println("元素 " + target + " 在索引 " + result);} else {System.out.println("元素 " + target + " 不在数组中");}}
}

代码详解：

初始化：low 和 high 分别指向数组的开头和末尾。
中间元素计算：mid = low + (high - low) / 2 计算中间索引，防止溢出。
查找逻辑：根据中间元素与目标元素的比较结果，调整 low 或 high 的值，缩小查找范围。
返回结果：如果找到目标元素，返回其索引；如果遍历完仍未找到，返回 -1 表示查找失败。

3.2 递归实现

public class BinarySearchRecursive {// 二分查找的递归实现public static int binarySearch(int[] arr, int target, int low, int high) {if (low > high) {return -1;  // 查找失败}int mid = low + (high - low) / 2;  // 避免整数溢出if (arr[mid] == target) {return mid;  // 找到目标} else if (arr[mid] < target) {return binarySearch(arr, target, mid + 1, high);  // 在右半部分递归查找} else {return binarySearch(arr, target, low, mid - 1);  // 在左半部分递归查找}}public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11, 13};int target = 7;int result = binarySearch(arr, target, 0, arr.length - 1);if (result != -1) {System.out.println("元素 " + target + " 在索引 " + result);} else {System.out.println("元素 " + target + " 不在数组中");}}
}

代码详解：

递归终止条件：当 low > high 时，说明查找范围为空，查找失败，返回 -1。
递归查找：通过比较中间元素与目标元素，将问题规模减半递归处理。

4. 二分搜索的时间复杂度

二分搜索的时间复杂度为 O(\log n)，因为每次查找都将问题规模减半。与线性搜索的 O(n) 相比，二分搜索效率更高，特别是在大规模数据中。

时间复杂度：O(log⁡n)
空间复杂度：
- 迭代版本的空间复杂度为 O(1)，因为只需要常数空间存储索引。
- 递归版本的空间复杂度为 O(log⁡n)，因为递归调用会占用栈空间。

5. 二分搜索的应用

5.1 数组查找

二分搜索最常见的应用是从有序数组中查找元素。由于其时间复杂度为 O(log⁡n)，特别适合在大规模数据中进行查找。

5.2 查找最小/最大满足条件的元素

二分搜索还可以用于查找某个条件下的最小或最大值。例如，在查找某个数值范围内满足某个条件的最大元素或最小元素时，二分搜索是一个高效的选择。

5.3 应用于算法优化

在很多算法问题中，二分搜索可以作为一个优化手段，例如在动态规划问题中寻找状态转移方程的最优值。

6. 二分搜索的变种

6.1 查找第一个大于或等于目标值的元素

除了精确查找目标值，二分搜索还可以用于查找第一个大于或等于目标值的元素。这在实际应用中也非常常见。

public static int lowerBound(int[] arr, int target) {int low = 0;int high = arr.length - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] >= target) {high = mid - 1;} else {low = mid + 1;}}return low;
}

解释：这个函数返回第一个大于或等于目标值 target 的索引。

6.2 查找最后一个小于或等于目标值的元素

类似的，可以使用二分搜索查找最后一个小于或等于目标值的元素。

public static int upperBound(int[] arr, int target) {int low = 0;int high = arr.length - 1;while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return high;
}

解释：这个函数返回最后一个小于或等于目标值 target 的索引。