如何用 Java 实现 Binary Search

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。其基本思想是通过不断将搜索范围减半，快速定位目标元素的位置。二分查找的时间复杂度为 O(log n)，适用于大规模数据的查找操作。

下面将详细介绍如何在 Java 中实现二分查找，并提供迭代和递归两种实现方式。

二分查找的前提条件

• 有序数组：二分查找要求输入的数组必须是有序的（通常是升序或降序）。
• 随机访问：由于每次比较后都需要访问数组的中间元素，因此数组需要支持高效的随机访问操作。

迭代实现

迭代实现的二分查找通过循环不断缩小搜索范围，直到找到目标元素或确定目标不存在。

public class BinarySearch {

    /**
     * 迭代方式实现二分查找
     *
     * @param arr    已排序的数组
     * @param target 目标值
     * @return 目标值的索引，如果未找到则返回 -1
     */
    public static int binarySearchIterative(int[] arr, int target) {
        int left = 0;                     // 搜索范围的左边界
        int right = arr.length - 1;         // 搜索范围的右边界

        while (left <= right) {
            // 防止 (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[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
        int target = 14;

        int result = binarySearchIterative(sortedArray, target);
        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引位置为: " + result);
        } else {
            System.out.println("元素 " + target + " 不存在于数组中。");
        }
    }
}

输出:

元素 14 在数组中的索引位置为: 6

递归实现

递归实现的二分查找通过函数自身不断缩小搜索范围，直到找到目标元素或确定目标不存在。

public class BinarySearchRecursive {

    /**
     * 递归方式实现二分查找
     *
     * @param arr    已排序的数组
     * @param target 目标值
     * @param left   搜索范围的左边界
     * @param right  搜索范围的右边界
     * @return 目标值的索引，如果未找到则返回 -1
     */
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 基本情况：未找到目标值
        }

        // 防止 (left + right) 可能导致的整数溢出
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分继续查找
        } else {
            return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分继续查找
        }
    }

    // 示例使用
    public static void main(String[] args) {
        int[] sortedArray = {3, 6, 8, 12, 14, 17, 20, 21, 24, 26};
        int target = 20;

        int result = binarySearchRecursive(sortedArray, target, 0, sortedArray.length - 1);
        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引位置为: " + result);
        } else {
            System.out.println("元素 " + target + " 不存在于数组中。");
        }
    }
}

输出:

元素 20 在数组中的索引位置为: 6

注意事项

1. 数组必须有序：二分查找只适用于已排序的数组。如果数组未排序，需先进行排序（例如使用 Arrays.sort() 方法）后再进行二分查找。

2. 处理重复元素：如果数组中存在多个相同的目标值，二分查找可能返回其中任意一个的索引。如果需要找到第一个或最后一个出现的位置，需要对算法进行适当修改。

3. 整数溢出：在计算中间索引 mid 时，使用 left + (right - left) / 2 而非 (left + right) / 2 可以避免当 left 和 right 都很大时可能发生的整数溢出。

4. 时间复杂度：二分查找的时间复杂度为 O(log n)，相比于线性查找的 O(n) 更加高效，尤其适用于大规模数据集。

扩展：查找第一个或最后一个出现的位置

如果数组中存在多个相同的目标值，可能需要查找目标值的第一个或最后一个出现的位置。以下是如何修改二分查找来实现这一功能。

查找第一个出现的位置

public static int binarySearchFirst(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 继续向左查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

查找最后一个出现的位置

public static int binarySearchLast(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // 继续向右查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

总结

二分查找是一种高效的查找算法，适用于在有序数组中快速定位目标元素。通过迭代或递归的方式实现二分查找，可以显著提高在大规模数据集上的搜索效率。在实际应用中，根据具体需求选择合适的实现方式，并注意处理边界情况和可能的整数溢出问题。