Java二分搜索如何处理重复元素

在Java中，使用二分搜索处理重复元素时，通常有两种方法：找到第一个出现的元素和找到最后一个出现的元素。这里我将分别介绍这两种方法的实现。

1. 找到第一个出现的元素：

public int findFirstOccurrence(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int result = -1;

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

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

    return result;
}

2. 找到最后一个出现的元素：

public int findLastOccurrence(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int result = -1;

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

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

    return result;
}

这两个方法的主要区别在于当找到目标元素时，一个是在左侧继续查找（寻找第一个出现的位置），另一个是在右侧继续查找（寻找最后一个出现的位置）。这样可以在O(log n)的时间复杂度内找到目标元素的第一个和最后一个出现的位置。