Java二分搜索如何处理边界条件

在Java中实现二分搜索时，处理边界条件是非常重要的，因为不当的处理可能导致数组越界异常或搜索结果不正确。以下是一些常见的边界条件及其处理方法：

1. 空数组

如果输入数组为空，直接返回一个表示未找到的值（例如 -1）。

if (array == null || array.length == 0) {
    return -1;
}

2. 单元素数组

如果数组只有一个元素，直接比较该元素与目标值。

if (array.length == 1) {
    return array[0] == target ? 0 : -1;
}

3. 目标值小于数组最小值

如果目标值小于数组中的最小值，直接返回 -1。

if (target < array[0]) {
    return -1;
}

4. 目标值大于数组最大值

如果目标值大于数组中的最大值，直接返回 -1。

if (target > array[array.length - 1]) {
    return -1;
}

5. 二分搜索的边界条件

在标准的二分搜索中，需要正确设置左右边界，并在每次迭代中更新这些边界。

public int binarySearch(int[] array, int target) {
    if (array == null || array.length == 0) {
        return -1;
    }

    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出

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

    return -1; // 未找到目标值
}

6. 处理重复元素

如果数组中存在重复元素，二分搜索可能返回任意一个匹配的索引。如果需要找到第一个或最后一个匹配的索引，可以稍微修改算法。

查找第一个匹配的索引

public int binarySearchFirst(int[] array, int target) {
    if (array == null || array.length == 0) {
        return -1;
    }

    int left = 0;
    int right = array.length - 1;
    int result = -1;

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

        if (array[mid] == target) {
            result = mid;
            right = mid - 1; // 继续在左侧查找
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

查找最后一个匹配的索引

public int binarySearchLast(int[] array, int target) {
    if (array == null || array.length == 0) {
        return -1;
    }

    int left = 0;
    int right = array.length - 1;
    int result = -1;

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

        if (array[mid] == target) {
            result = mid;
            left = mid + 1; // 继续在右侧查找
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

通过这些方法，可以有效地处理二分搜索中的各种边界条件，确保算法的正确性和鲁棒性。