二分搜索在java中怎么用

在 Java 中，二分搜索（Binary Search）通常用于已排序的数组或集合。Java 提供了现成的 API，也支持自己手写实现。

一、使用 Java 自带的 Arrays.binarySearch

1️⃣ 对数组使用（最常用）

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};

        int index = Arrays.binarySearch(arr, 7);
        System.out.println(index); // 输出 3

        int notFound = Arrays.binarySearch(arr, 4);
        System.out.println(notFound); // 负数，表示不存在
    }
}

✅ 注意：

• 数组必须升序排序
• 找到：返回索引
• 没找到：返回 负数（-(插入点) - 1）

2️⃣ 对对象数组使用（需实现 Comparable）

import java.util.Arrays;

class Student implements Comparable<Student> {
    int score;
    Student(int score) { this.score = score; }

    public int compareTo(Student o) {
        return Integer.compare(this.score, o.score);
    }
}

public class Main {
    public static void main(String[] args) {
        Student[] students = {
            new Student(60), new Student(75), new Student(90)
        };
        int index = Arrays.binarySearch(students, new Student(75));
        System.out.println(index);
    }
}

二、使用 Collections.binarySearch（List）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 3, 5, 7, 9);
        int index = Collections.binarySearch(list, 5);
        System.out.println(index); // 2
    }
}

⚠️ List 也必须是有序的。

三、手写二分搜索（面试/理解原理）

public class BinarySearch {
    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[] arr = {1, 3, 5, 7, 9};
        System.out.println(binarySearch(arr, 7)); // 3
    }
}

✅ 推荐使用 mid = left + (right - left) / 2 防止溢出。

四、常见易错点

❌ 数组未排序就使用 binarySearch
❌ 用返回值 >= 0 判断存在（负数不代表错误）
❌ 手写时 left <= right 写错成 <

五、什么时候用二分？

• 数组 / List 已排序
• 查找频繁、数据量大
• 时间复杂度：O(log n)

如果你愿意，我也可以讲：

• 二分搜索的变种（左边界 / 右边界）
• 在旋转数组中二分
• 二分在算法题中的套路

你想看哪一个？