Java 二分查找代码解析

简介

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。相较于线性查找，它通过每次将搜索区间减半，大大减少了查找所需的时间复杂度，从线性时间 $O(n)$ 降低到对数时间 $O(\log n)$。在 Java 中，实现二分查找有多种方式，本文将详细探讨其基础概念、使用方法、常见实践以及最佳实践。

基础概念

二分查找的核心思想是利用数组的有序性。给定一个有序数组和一个目标值，算法首先确定数组的中间位置。如果中间位置的元素等于目标值，则查找成功。如果中间元素大于目标值，则目标值只可能存在于数组的左半部分；反之，如果中间元素小于目标值，则目标值只可能在数组的右半部分。通过不断重复这个过程，逐步缩小搜索范围，直到找到目标值或确定目标值不存在。

使用方法

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 目标值不存在
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearch(arr, target, left, mid - 1);
        } else {
            return binarySearch(arr, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        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 + " 不存在于数组中");
        }
    }
}

迭代实现

public class BinarySearchIterative {
    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) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1; // 目标值不存在
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("目标值 " + target + " 位于索引 " + result);
        } else {
            System.out.println("目标值 " + target + " 不存在于数组中");
        }
    }
}

常见实践

查找整数

上述代码示例展示了如何在整数数组中进行二分查找。在实际应用中，这种方法常用于查找有序列表中的特定整数，例如学生成绩排名列表、股票价格序列等。

查找对象

当需要在对象数组中进行二分查找时，对象必须实现 Comparable 接口，或者在二分查找方法中提供自定义的比较器。

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

class Person implements Comparable<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 int compareTo(Person other) {
        return this.age - other.age;
    }
}

public class BinarySearchObject {
    public static <T> int binarySearch(T[] arr, T target, Comparator<? super T> comparator) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = comparator.compare(arr[mid], target);
            if (cmp == 0) {
                return mid;
            } else if (cmp > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 25),
            new Person("Bob", 30),
            new Person("Charlie", 35)
        };
        Person target = new Person("Bob", 30);
        Comparator<Person> ageComparator = Comparator.comparingInt(Person::getAge);
        int result = binarySearch(people, target, ageComparator);
        if (result != -1) {
            System.out.println("目标对象位于索引 " + result);
        } else {
            System.out.println("目标对象不存在于数组中");
        }
    }
}

最佳实践

处理边界情况

在实现二分查找时，需要特别注意边界情况，例如数组为空、目标值在数组的两端等。确保在这些特殊情况下算法的正确性。

性能优化

虽然二分查找本身已经是一种高效的算法，但在某些情况下，还可以进一步优化。例如，在计算中间位置时，使用 left + (right - left) / 2 而不是 (left + right) / 2，可以避免整数溢出的问题。

小结

二分查找是 Java 编程中一项重要的算法技巧，它在处理有序数据时具有高效性。通过递归和迭代两种方式的实现，以及在查找整数和对象中的应用，我们深入了解了二分查找的使用方法。同时，关注边界情况和性能优化是确保算法正确性和高效性的关键。

参考资料

《Effective Java》
Oracle Java Documentation
Wikipedia: Binary Search Algorithm

希望本文能帮助读者更好地理解和应用 Java 中的二分查找代码。如有任何疑问或建议，欢迎在评论区留言。