Java Binary Search 如何处理重复元素

在Java中，二分查找算法通常用于在有序数组中查找特定元素。当数组中存在重复元素时，二分查找可能会返回其中一个匹配元素的索引，但不一定是第一个或最后一个。如果你需要找到第一个或最后一个匹配元素的索引，可以对标准的二分查找算法进行一些修改。

以下是一个Java示例，展示了如何在有序数组中找到目标值的第一个和最后一个索引：

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 2, 3, 4, 5};
        int target = 2;

        int firstIndex = findFirstIndex(arr, target);
        int lastIndex = findLastIndex(arr, target);

        System.out.println("First index of " + target + ": " + firstIndex);
        System.out.println("Last index of " + target + ": " + lastIndex);
    }

    public static int findFirstIndex(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;

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

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

        return result;
    }

    public static int findLastIndex(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;

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

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

        return result;
    }
}

在这个示例中，findFirstIndex方法用于查找目标值的第一个索引，findLastIndex方法用于查找目标值的最后一个索引。这两个方法都使用了二分查找算法，并在找到目标值时继续在左侧或右侧查找，以确保找到的是第一个或最后一个匹配元素的索引。