Java 数组中的二分查找

简介

二分查找（Binary Search）是一种在有序数组中高效查找目标值的算法。相比于顺序查找需要遍历整个数组，二分查找每次都能将搜索范围缩小一半，大大提高了查找效率。在 Java 中，利用数组的有序特性使用二分查找可以快速定位到所需元素的位置。本文将详细介绍 Java 数组中二分查找的相关知识，包括基础概念、使用方法、常见实践以及最佳实践。

二分查找基础概念

二分查找的核心思想是将有序数组分成两部分，通过比较目标值与数组中间元素的大小，决定继续在左半部分还是右半部分进行查找。每次迭代都能排除一半的元素，直到找到目标值或者确定目标值不存在于数组中。

例如，对于有序数组 [1, 3, 5, 7, 9]，如果要查找值 5： 1. 首先找到中间元素 5（索引为 2）。 2. 目标值 5 等于中间元素，查找成功，返回索引 2。

如果要查找值 6： 1. 找到中间元素 5，因为 6 > 5，所以在右半部分 [7, 9] 继续查找。 2. 新的中间元素是 7，因为 6 < 7，所以在左半部分（此时左半部分没有元素了）继续查找，最终确定 6 不存在于数组中，返回一个负数（通常是插入点的负数 - 1）。

使用方法

利用 `Arrays.binarySearch` 方法

Java 的 java.util.Arrays 类提供了 binarySearch 方法来执行二分查找。该方法有多个重载版本，最常用的形式如下：

import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        int target = 5;
        int result = Arrays.binarySearch(array, target);
        if (result >= 0) {
            System.out.println("目标值 " + target + " 找到，索引为: " + result);
        } else {
            System.out.println("目标值 " + target + " 未找到，插入点为: " + (-result - 1));
        }
    }
}

在上述代码中： 1. 定义了一个有序整数数组 array。 2. 设定目标值 target 为 5。 3. 使用 Arrays.binarySearch(array, target) 方法进行查找。 4. 根据返回值判断目标值是否找到。如果返回值大于等于 0，表示找到目标值，返回值即为索引；如果返回值为负数，表示未找到，(-result - 1) 为目标值应该插入的位置。

手动实现二分查找

手动实现二分查找可以更好地理解其原理。以下是一个简单的 Java 实现：

public class ManualBinarySearch {
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9};
        int target = 5;
        int result = binarySearch(array, target);
        if (result >= 0) {
            System.out.println("目标值 " + target + " 找到，索引为: " + result);
        } else {
            System.out.println("目标值 " + target + " 未找到");
        }
    }
}

在这个实现中： 1. 定义了 binarySearch 方法，接收一个整数数组 array 和目标值 target。 2. 使用 left 和 right 指针分别表示搜索范围的左右边界。 3. 在 while 循环中，计算中间索引 mid。 4. 根据中间元素与目标值的比较结果，调整 left 或 right 指针，直到找到目标值或搜索范围为空。

常见实践

查找整数

在实际应用中，经常需要在整数数组中查找特定的整数。例如，在一个学生成绩数组中查找某个成绩：

import java.util.Arrays;

public class StudentGradeSearch {
    public static void main(String[] args) {
        int[] grades = {60, 70, 80, 90, 95};
        int targetGrade = 80;
        int result = Arrays.binarySearch(grades, targetGrade);
        if (result >= 0) {
            System.out.println("成绩 " + targetGrade + " 找到，索引为: " + result);
        } else {
            System.out.println("成绩 " + targetGrade + " 未找到，插入点为: " + (-result - 1));
        }
    }
}

查找对象

二分查找不仅可以用于基本数据类型数组，还可以用于对象数组。但是，对象数组必须实现 Comparable 接口或者提供一个 Comparator。例如，有一个 Person 类，按照年龄排序后进行二分查找：

import java.util.Arrays;
import java.util.Comparator;

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class PersonSearch {
    public static void main(String[] args) {
        Person[] people = {
                new Person("Alice", 20),
                new Person("Bob", 25),
                new Person("Charlie", 30)
        };

        // 使用 Comparator 按照年龄排序
        Arrays.sort(people, Comparator.comparingInt(Person::getAge));

        Person targetPerson = new Person("Bob", 25);
        int result = Arrays.binarySearch(people, targetPerson, Comparator.comparingInt(Person::getAge));
        if (result >= 0) {
            System.out.println("目标对象找到，索引为: " + result);
        } else {
            System.out.println("目标对象未找到，插入点为: " + (-result - 1));
        }
    }
}

在上述代码中： 1. 定义了 Person 类，包含 name 和 age 字段。 2. 使用 Arrays.sort 方法结合 Comparator 按照年龄对 Person 对象数组进行排序。 3. 使用 Arrays.binarySearch 方法结合相同的 Comparator 查找目标 Person 对象。

最佳实践

确保数组有序

二分查找的前提是数组必须有序。在使用二分查找之前，务必先对数组进行排序。可以使用 Arrays.sort 方法对基本数据类型数组进行排序，对于对象数组，需要确保对象实现 Comparable 接口或者提供合适的 Comparator。

处理边界情况

在手动实现二分查找时，要特别注意处理边界情况。例如，确保 left 和 right 指针的移动不会导致数组越界，以及正确处理目标值不存在于数组中的情况。

性能优化

虽然二分查找的时间复杂度为 O(log n)，已经非常高效，但在一些极端情况下，还可以进一步优化。例如，在数组非常大时，可以考虑使用并行算法来提高查找速度。另外，避免不必要的计算，如在计算中间索引 mid 时，使用 left + (right - left) / 2 而不是 (left + right) / 2，可以防止整数溢出。

小结

二分查找是在 Java 数组中进行高效查找的重要算法。通过理解其基础概念、掌握使用方法，并遵循最佳实践，可以在各种应用场景中快速准确地找到目标值。无论是查找基本数据类型还是对象，二分查找都能显著提高查找效率，节省时间和资源。

参考资料

Oracle Java 官方文档 - Arrays 类
《Effective Java》 - Joshua Bloch

希望通过本文，读者能深入理解并高效使用 Java 数组中的二分查找。在实际开发中，灵活运用二分查找可以优化程序性能，提高用户体验。