使用 BinarySearch 查找元素的第一次和最后一次出现

Question

我可以高效地找到第一次出现的地方，但找不到最后一次出现的地方。我得到的最后一次出现的元素的答案总是正确的索引加一。

这是我的代码：

class FirstAndLastOccurence{

    public static int first(int[] arr, int n, int x){
        int left = 0;
        int right = n-1;
        int res = -1;

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

            if(x < arr[mid])
                right = mid-1;
            if(x > arr[mid])
                left = mid+1;
            else{
                res = mid;
                right = mid-1;
            }
        }

        return res;
    }

    public static int last(int[] arr, int n, int x){
        int left = 0;
        int right = n-1;
        int res = -1;

        while(left <= right){
            int mid = left + (right-left)/2;
            
            if(x < arr[mid])
                right = mid-1;
            if(x > arr[mid])
                left = mid+1;
            else{
                res = mid;
                left = mid+1;
            }
        }

        return res;
    }

    public static void main(String[] args){
        int[] arr = new int[]{2, 4, 10, 10, 10, 10, 56, 71, 90};
        System.out.println(first(arr, arr.length, 10));
        System.out.println(last(arr, arr.length, 10));
    }
}

输出：

2
6

第一个输出是正确的，而我的最后一个输出是错误的，因为它应该是 5。我尝试遵循的代码是 here（代码不完全相同，我是以我个人更熟悉的方式实现二进制搜索）。

Answer 1

您在最后添加了 if 语句和 else 语句，仅针对第二个 if 语句执行，这是不正确的。请找到以下有效并给出正确答案的代码。

public static int last(int[] arr, int n, int x){
    int left = 0;
    int right = n-1;
    int res = -1;

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

        if(x < arr[mid])
            right = mid-1;
        else if(x > arr[mid])
            left = mid+1;
        else{
            res = mid;
            left = mid+1;
        }
    }

    return res;
}

使用 BinarySearch 查找元素的第一次和最后一次出现

Finding first and last occurrence of an element using BinarySearch

java

binary-search