Java二分搜索如何处理边界情况

在Java中实现二分搜索时，处理边界情况是非常重要的，因为这关系到算法的正确性和效率。以下是一些常见的边界情况和处理方法：

1. 空数组

如果数组为空，二分搜索应该返回一个表示未找到的值，通常是 -1 或者 null。

public int binarySearch(int[] array, int target) {
    if (array == null || array.length == 0) {
        return -1; // 或者返回 null
    }
    // 继续二分搜索
}

2. 单元素数组

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

public int binarySearch(int[] array, int target) {
    if (array == null || array.length == 0) {
        return -1;
    }
    if (array.length == 1) {
        return array[0] == target ? 0 : -1;
    }
    // 继续二分搜索
}

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

如果目标值小于数组中的最小值，二分搜索应该返回 -1。

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;
        }
    }
    // 如果目标值小于数组最小值
    if (left == 0 && array[0] > target) {
        return -1;
    }
    return left;
}

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

如果目标值大于数组中的最大值，二分搜索应该返回 -1。

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;
        }
    }
    // 如果目标值大于数组最大值
    if (right == array.length - 1 && array[right] < target) {
        return -1;
    }
    return right + 1;
}

5. 数组中有重复元素

如果数组中有重复元素，二分搜索可以返回任意一个匹配的索引。如果需要返回第一个或最后一个匹配的索引，可以进行相应的调整。

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;
}

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