每日算法 — 使用java实现二分搜索：有序数据中的对数级查找

二分搜索（Binary Search）是计算机科学中最经典、最高效的查找算法之一。它的核心思想非常简单：每次将搜索区间缩小一半，从而在有序数据中实现 (O(\log n)) 的时间复杂度。本文将用 Java 完整实现二分搜索，并通过一个”价格竞猜”小游戏带你深入理解其原理与变种。

算法原理

假设我们有一个升序排列的数组，要查找目标值 target：

初始化左右指针 left = 0，right = n - 1。
计算中间位置 mid = left + (right - left) / 2（防止溢出）。
比较 nums[mid] 与 target：
若相等，返回 mid。
若 nums[mid] < target，说明目标在右半区，left = mid + 1。
若 nums[mid] > target，说明目标在左半区，right = mid - 1。
重复步骤 2-3，直到找到目标或 left > right。

为什么时间复杂度是 (O(\log n))？
每次循环都将搜索范围减半，最坏情况下需要 (\log_2 n) 次即可确定结果。

基础实现

public class BinarySearch {

    /**
     * 标准二分搜索：在有序数组中查找目标值的索引
     * @param nums 升序排列的整数数组
     * @param target 待查找的目标值
     * @return 目标值的索引，若不存在则返回 -1
     */
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // 使用此写法避免 (left + right) 可能导致的整数溢出
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid; // 找到目标，直接返回索引
            } else if (nums[mid] < target) {
                left = mid + 1; // 目标在右半区，收缩左边界
            } else {
                right = mid - 1; // 目标在左半区，收缩右边界
            }
        }
        return -1; // 未找到目标
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 13;
        int result = binarySearch(nums, target);
        System.out.println("目标 " + target + " 的索引为: " + result);
        // 输出: 目标 13 的索引为: 6
    }
}

高级变种：查找边界与插入位置

在实际工程中，我们经常需要查找目标值的左边界（第一个等于 target 的位置）或右边界（最后一个等于 target 的位置）。以下代码展示了如何优雅地处理这些场景：

public class BinarySearchAdvanced {

    /**
     * 查找目标值的左边界（第一个等于 target 的索引）
     * 若不存在，返回应该插入的位置（保持有序）
     */
    public static int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 注意：right 开区间

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid; // 相等时也向左收缩，确保找到最左侧
            }
        }
        return left;
    }

    /**
     * 查找目标值的右边界（最后一个等于 target 的索引）
     * 返回的是 target 之后的位置，实际索引需减 1
     */
    public static int upperBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1; // 相等时向右收缩，确保找到最右侧之后的位置
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 4, 4, 5, 7};
        int target = 4;

        int left = lowerBound(nums, target);
        int right = upperBound(nums, target) - 1;

        System.out.println("左边界索引: " + left);  // 2
        System.out.println("右边界索引: " + right); // 4
        System.out.println("出现次数: " + (right - left + 1)); // 3
    }
}

实战应用：价格竞猜游戏

下面我们用二分搜索的思想实现一个”猜价格”小游戏。程序随机生成一个 1~1000 之间的价格，玩家通过输入猜测，程序根据二分搜索策略给出”高了”或”低了”的提示，并统计猜测次数：

import java.util.Random;
import java.util.Scanner;

public class PriceGuessingGame {

    private final int secretPrice;
    private int guessCount;

    public PriceGuessingGame() {
        this.secretPrice = new Random().nextInt(1000) + 1;
        this.guessCount = 0;
    }

    /**
     * 模拟最优猜测策略：使用二分搜索在 1~1000 范围内定位价格
     * 最多只需要 log2(1000) ≈ 10 次即可猜中
     */
    public void playWithOptimalStrategy() {
        int low = 1;
        int high = 1000;

        System.out.println("商品价格在 1~1000 之间，开始猜测...");

        while (low <= high) {
            int guess = low + (high - low) / 2;
            guessCount++;
            System.out.println("第 " + guessCount + " 次猜测: " + guess);

            if (guess == secretPrice) {
                System.out.println("恭喜猜中！价格就是 " + secretPrice);
                System.out.println("总共猜测了 " + guessCount + " 次（理论最优 ≤10 次）");
                return;
            } else if (guess < secretPrice) {
                System.out.println("  → 太低了！");
                low = guess + 1;
            } else {
                System.out.println("  → 太高了！");
                high = guess - 1;
            }
        }
    }

    /**
     * 允许人类玩家互动猜测
     */
    public void playInteractive() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("猜价格游戏！价格在 1~1000 之间，请输入你的猜测：");

        while (true) {
            System.out.print("你的猜测: ");
            int guess = scanner.nextInt();
            guessCount++;

            if (guess == secretPrice) {
                System.out.println("恭喜！你用了 " + guessCount + " 次猜中了价格 " + secretPrice);
                break;
            } else if (guess < secretPrice) {
                System.out.println("太低了，再试试！");
            } else {
                System.out.println("太高了，再试试！");
            }
        }
        scanner.close();
    }

    public static void main(String[] args) {
        PriceGuessingGame game = new PriceGuessingGame();
        // 演示最优策略
        game.playWithOptimalStrategy();
    }
}

复杂度分析

指标	时间复杂度	空间复杂度
标准二分搜索	(O(\log n))	(O(1))
查找边界	(O(\log n))	(O(1))
线性搜索（对比）	(O(n))	(O(1))

常见陷阱与注意事项

整数溢出：务必使用 mid = left + (right - left) / 2，而非 (left + right) / 2。
边界条件：left <= right 与 left < right 的选择决定了搜索区间的开闭，需与逻辑保持一致。
循环终止：确保每次循环至少有一个指针移动，避免死循环。

总结

二分搜索的魅力在于其极简的思想和极高的效率。掌握标准版本后，灵活变通处理边界问题是面试和工程中的高频考点。通过”价格竞猜”游戏，我们不仅理解了算法的执行流程，更体会到了 (O(\log n)) 相比 (O(n)) 的巨大优势。

Tagged with: Binary Search Java算法二分搜索对数级复杂度有序查找贪心