Java二分搜索如何处理单元素数组

在Java中，二分搜索（Binary Search）是一种高效的查找算法，适用于已排序的数组。对于单元素数组，二分搜索同样适用，因为它的基本思想是将搜索范围逐步缩小一半，直到找到目标元素或确定目标元素不存在。

以下是使用Java实现二分搜索的示例代码，特别处理了单元素数组的情况：

public class BinarySearch {
    public static 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; // 目标元素不存在
    }

    public static void main(String[] args) {
        int[] singleElementArray = {5};
        int target = 5;
        int result = binarySearch(singleElementArray, target);
        System.out.println("Target found at index: " + result); // 输出: Target found at index: 0

        target = 10;
        result = binarySearch(singleElementArray, target);
        System.out.println("Target found at index: " + result); // 输出: Target found at index: -1
    }
}

代码解释

1. 初始检查：首先检查数组是否为空或长度为0，如果是，则返回-1表示目标元素不存在。
2. 初始化边界：设置搜索范围的左右边界，left初始为0，right初始为数组长度减1。
3. 循环搜索：在left <= right的条件下进行循环，计算中间索引mid，并根据array[mid]与目标值target的比较结果调整搜索范围。
   • 如果array[mid] == target，则找到目标元素，返回mid。
   • 如果array[mid] < target，则目标元素在右半部分，更新left为mid + 1。
   • 如果array[mid] > target，则目标元素在左半部分，更新right为mid - 1。
4. 未找到目标元素：如果循环结束仍未找到目标元素，返回-1。

单元素数组的处理

对于单元素数组，二分搜索的初始搜索范围是[0, 0]，即只有一个元素。算法会立即比较这个元素与目标值，并返回相应的结果。

通过这种方式，二分搜索能够高效地处理单元素数组，时间复杂度为O(log n)，其中n是数组的长度。