Java中如何编写二分搜索代码

在Java中，二分搜索（Binary Search）是一种高效的查找算法，适用于已排序的数组或列表。它通过反复将搜索范围分成两半来缩小目标元素的位置。以下是二分搜索的两种常见实现方式：迭代法和递归法。

1. 迭代法实现二分搜索

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

2. 递归法实现二分搜索

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, 9, 12, 15, 18, 21, 24, 27, 30};
        int target = 21;

        int result = binarySearchRecursive(sortedArray, target, 0, sortedArray.length - 1);

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

输出:

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

注意事项

1. 数组必须是有序的：二分搜索只能在已排序的数组或列表中正确工作。如果数组未排序，结果将不可靠。

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

3. 防止整数溢出：在计算中间索引 mid 时，使用 left + (right - left) / 2 而不是 (left + right) / 2，以防止 left + right 可能导致的整数溢出。

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

使用Java内置方法

Java标准库中的 Arrays 类已经提供了二分搜索的方法，可以直接使用：

import java.util.Arrays;

public class BinarySearchBuiltIn {
    public static void main(String[] args) {
        int[] sortedArray = {5, 10, 15, 20, 25, 30, 35};
        int target = 20;

        // Arrays.binarySearch 返回 (a[i] == key) ? i : -(i+1)
        int index = Arrays.binarySearch(sortedArray, target);

        if (index >= 0) {
            System.out.println("元素 " + target + " 在数组中的索引位置为: " + index);
        } else {
            // 如果返回值为负数，则表示未找到，且 -(insertion point) - 1
            int insertionPoint = -(index + 1);
            System.out.println("元素 " + target + " 不在数组中。应插入的位置为: " + insertionPoint);
        }
    }
}

输出:

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

使用内置方法不仅简化了代码，还提高了可读性和可靠性。但在某些情况下，如需要自定义搜索逻辑时，自行实现二分搜索是必要的。