搜索算法之二分搜索详细解读（附带Java代码解读）

1. 基本概念

二分搜索（Binary Search）是一种高效的查找算法，用于在一个已排序的数组中查找特定元素。它通过逐步将搜索范围减少一半来实现搜索，从而比线性搜索更快。由于它利用了数组的有序性，能够在对数时间内完成搜索操作。

2. 工作原理

二分搜索的基本思想是：

1. 初始化：设置两个指针，left 和 right，分别指向数组的开始和结束位置。

2. 中间点：计算当前搜索范围的中间点 mid，即 (left + right) / 2。

3. 比较：

   • 如果 arr[mid] 等于目标值 target，则找到目标值，返回 mid。
   • 如果 arr[mid] 大于目标值 target，则目标值在 left 到 mid - 1 之间，调整 right 为 mid - 1。
   • 如果 arr[mid] 小于目标值 target，则目标值在 mid + 1 到 right 之间，调整 left 为 mid + 1。

4. 结束条件：重复步骤 2 和 3，直到 left 超过 right。如果在这个过程中没有找到目标值，返回 -1，表示目标值不在数组中。

3. 算法步骤

以下是二分搜索的详细步骤：

1. 输入：

   • 一个已排序的整数数组 arr。
   • 一个目标值 target。

2. 步骤：

   • 设置 left 为 0。
   • 设置 right 为 arr.length - 1。
   • 进入循环，直到 left 小于或等于 right：
     • 计算中间点 mid：mid = (left + right) / 2。
     • 如果 arr[mid] 等于 target，返回 mid。
     • 如果 arr[mid] 大于 target，将 right 设置为 mid - 1。
     • 如果 arr[mid] 小于 target，将 left 设置为 mid + 1。
   • 如果循环结束后仍未找到目标值，返回 -1。

4. 时间复杂度分析

• 最坏情况：每次比较后，搜索范围缩小一半。对于长度为 n 的数组，最多需要 log2(n) + 1 次比较，时间复杂度为 O(log n)。

• 最佳情况：目标值恰好是中间元素，时间复杂度为 O(1)。

• 平均情况：时间复杂度为 O(log n)，因为每次搜索范围减少一半。

5. 空间复杂度

• 空间复杂度：二分搜索只需要常数级别的额外空间来存储变量 left、right 和 mid，因此空间复杂度为 O(1)。

6. 实现代码

public class BinarySearch {

    /**
     * 执行二分搜索
     * @param arr 已排序的数组
     * @param target 目标值
     * @return 目标值的索引，如果未找到返回-1
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0; // 搜索范围的左边界
        int right = arr.length - 1; // 搜索范围的右边界

        while (left <= right) {
            int mid = left + (right - left) / 2; // 计算中间点
            
            if (arr[mid] == target) {
                return mid; // 找到目标值，返回索引
            } else if (arr[mid] < target) {
                left = mid + 1; // 目标值在右半边，调整左边界
            } else {
                right = mid - 1; // 目标值在左半边，调整右边界
            }
        }
        
        return -1; // 未找到目标值
    }

    public static void main(String[] args) {
        // 示例数组（已排序）
        int[] numbers = {1, 2, 4, 7, 9, 10, 15};

        // 目标值
        int target = 7;

        // 执行二分搜索
        int result = binarySearch(numbers, target);

        // 输出搜索结果
        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引是: " + result);
        } else {
            System.out.println("元素 " + target + " 不在数组中。");
        }
    }
}

代码解读：

• public static int binarySearch(int[] arr, int target)：

  • 定义了一个静态方法 binarySearch，接受两个参数：一个已排序的整数数组 arr 和一个目标值 target。
  • 方法返回目标值的索引，如果未找到则返回 -1。

• int left = 0; int right = arr.length - 1;：

  • 初始化 left 为数组的第一个索引，right 为数组的最后一个索引。

• while (left <= right)：

  • 只要 left 小于或等于 right，继续搜索。

• int mid = left + (right - left) / 2;：

  • 计算中间点 mid。使用 left + (right - left) / 2 避免了可能的整数溢出。

• if (arr[mid] == target)：

  • 如果中间点的元素等于目标值，返回 mid。

• else if (arr[mid] < target)：

  • 如果中间点的元素小于目标值，将 left 移动到 mid + 1。

• else：

  • 如果中间点的元素大于目标值，将 right 移动到 mid - 1。

• return -1;：

  • 如果搜索范围为空，返回 -1，表示目标值不在数组中。

7. 实际应用

• 已排序数据：二分搜索要求数据必须是已排序的。它在有序数组、二叉搜索树等数据结构中非常高效。

• 查找操作：适用于需要频繁查找操作的场景，如字典查找、数据库索引等。

• 优化：对于大规模数据集和需要快速查找的情况，二分搜索是非常有效的选择。

8. 变体和改进

• 递归实现：二分搜索也可以用递归实现，通过将问题分解为子问题来求解。

• 插值查找：在均匀分布的数据中，插值查找比二分查找更快，通过更智能地选择中间点来减少搜索时间。

• 扩展应用：如在浮点数数组中的查找、寻找插入位置等。