Java 中的二分查找（Binary Search）

简介

二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找特定元素的高效算法。与顺序查找相比，二分查找的时间复杂度为 O(log n)，大大提高了查找效率。在 Java 中，有多种方式可以实现二分查找，本文将深入探讨其基础概念、使用方法、常见实践以及最佳实践。

基础概念

二分查找的核心思想是将有序数组分成两部分，每次通过比较目标值与中间元素的大小，决定在左半部分还是右半部分继续查找。具体步骤如下： 1. 设定两个指针，left 和 right，分别指向数组的开始和结束位置。 2. 计算中间位置 mid = left + (right - left) / 2。 3. 比较目标值 target 与 arr[mid]： - 如果 target == arr[mid]，则找到目标值，返回 mid。 - 如果 target < arr[mid]，则将 right 指针移动到 mid - 1，继续在左半部分查找。 - 如果 target > arr[mid]，则将 left 指针移动到 mid + 1，继续在右半部分查找。 4. 重复步骤 2 和 3，直到 left > right，表示未找到目标值，返回 -1。

使用方法

标准库中的二分查找

Java 的 java.util.Arrays 类提供了二分查找的方法。以下是使用示例：

import java.util.Arrays;

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

手写二分查找实现

public class ManualBinarySearch {
    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, 11, 13};
        int target = 7;
        int result = binarySearch(arr, target);
        if (result >= 0) {
            System.out.println("目标值 " + target + " 找到，索引为: " + result);
        } else {
            System.out.println("目标值 " + target + " 未找到");
        }
    }
}

常见实践

查找目标值

上述代码示例已经展示了如何在有序数组中查找目标值。这是二分查找最基本的应用场景。

查找目标值的插入位置

有时我们需要找到一个目标值应该插入到有序数组中的位置。以下是实现方法：

public class InsertionPosition {
    public static int searchInsertPosition(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

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

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

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 8;
        int result = searchInsertPosition(arr, target);
        System.out.println("目标值 " + target + " 的插入位置为: " + result);
    }
}

最佳实践

边界条件处理

空数组：在进行二分查找之前，先检查数组是否为空。如果为空，直接返回 -1 表示未找到。
处理溢出：计算中间位置时，使用 left + (right - left) / 2 而不是 (left + right) / 2，以避免 left + right 可能导致的溢出。

性能优化

数据类型选择：根据实际情况选择合适的数据类型。例如，如果数组元素范围较小，可以使用 byte 或 short 类型以节省内存。
减少比较次数：在某些情况下，可以通过提前判断数组边界或使用更高效的比较逻辑来减少比较次数。

小结

二分查找是一种高效的查找算法，在 Java 中可以通过标准库或手写实现。理解其基础概念、掌握使用方法以及遵循最佳实践，能够帮助我们在处理有序数组查找问题时提高效率和代码质量。无论是查找目标值还是确定插入位置，二分查找都展现出其独特的优势。

参考资料

Oracle Java 官方文档 - Arrays 类
《算法导论》（Thomas H. Cormen 等著）

希望通过本文，读者能够深入理解并高效使用 Java 中的二分查找算法。在实际应用中，根据具体需求灵活运用二分查找及其优化策略，能够为程序性能带来显著提升。