Java 二分查找代码详解

简介

二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找特定元素的高效算法。在 Java 编程中，掌握二分查找的代码实现和应用场景对于提高程序的性能至关重要。本文将深入探讨 Java 中二分查找代码的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地理解和运用这一强大的算法。

基础概念

二分查找的基本思想是将有序数组分成两部分，通过比较目标元素与数组中间元素的大小，决定在数组的前半部分还是后半部分继续查找，从而逐步缩小查找范围，直到找到目标元素或确定目标元素不存在。二分查找的时间复杂度为 O(log n)，相比线性查找的 O(n) 有显著的性能提升。

使用方法

递归实现

递归实现二分查找，代码如下：

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("元素未找到");
        } else {
            System.out.println("元素在索引 " + result + " 处找到");
        }
    }
}

迭代实现

迭代实现二分查找，代码如下：

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("元素未找到");
        } else {
            System.out.println("元素在索引 " + result + " 处找到");
        }
    }
}

常见实践

在整数数组中查找元素

上述代码示例展示了如何在整数数组中使用二分查找来查找特定元素。在实际应用中，整数数组的二分查找常用于排序后的数值数据检索场景，如查找用户 ID、订单编号等。

在自定义对象数组中查找元素

当需要在自定义对象数组中使用二分查找时，需要确保自定义对象实现了 Comparable 接口或提供一个 Comparator。以下是一个在自定义对象数组中使用二分查找的示例：

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 BinarySearchCustomObject {
    public static int binarySearch(Person[] arr, Person target) {
        int left = 0;
        int right = arr.length - 1;

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

            int comparison = arr[mid].compareTo(target);

            if (comparison == 0) {
                return mid;
            } else if (comparison > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

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

        Person target = new Person("Bob", 25);
        Arrays.sort(people);
        int result = binarySearch(people, target);

        if (result == -1) {
            System.out.println("元素未找到");
        } else {
            System.out.println("元素在索引 " + result + " 处找到");
        }
    }
}

最佳实践

注意事项

数组必须有序：二分查找的前提是数组已经排序，否则算法无法正常工作。
边界条件处理：在实现二分查找时，需要注意处理边界条件，如数组为空、目标元素不存在等情况。

性能优化

减少计算量：在计算中间索引时，使用 left + (right - left) / 2 而不是 (left + right) / 2，以避免整数溢出。
缓存中间结果：在多次查找相同数组时，可以缓存排序后的数组，以减少排序的开销。

小结

本文详细介绍了 Java 中二分查找代码的基础概念、使用方法、常见实践以及最佳实践。通过递归和迭代两种方式实现二分查找，并展示了在整数数组和自定义对象数组中的应用。在实际编程中，合理运用二分查找可以显著提高程序的性能，减少查找时间。希望读者通过本文的学习，能够更好地掌握和运用二分查找算法。