java - 递归查找排序数组中第一次出现的数字

Question

我想在排序数组中查找给定数字x 的第一次出现。这是我到目前为止的方法:

public static int firstOccur(int[] A, int x, int start, int end){

    int first = start;
    int last = end;
    int result = -1;

    while (first <= last){
        int mid = (first+last)/2;

        if(A[mid] == x){
            result = mid;   
            firstOccur(A, x, first, mid-1);
            return result;
        }
        else if(A[mid] < x){
            first = mid+1;
            result = firstOccur(A, x, first, last);
        }
        else if(A[mid] > x){
            last = mid-1;
            return firstOccur(A, x, first, last);
        }
    }
    return result;
}

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    System.out.print("Please enter the value you are looking for: ");
    int val = sc.nextInt();

    int[] arr = {1,2,2,2,5};
    System.out.println("The first occurence of " + val + " is at index " + firstOccur(arr, val, 0, arr.length-1));

}

当我运行代码时，该函数适用于数字1和5以及添加的任何内容。不幸的是，当提交x=2时，它返回索引2，这是不正确的。我是否遗漏了一个小细节？

Answer 1

这里你没有考虑递归函数的返回值

if(A[mid] == x){
    result = mid;   
    firstOccur(A, x, first, mid-1);
    return result;
}

更改为

if(A[mid] == x) {
    result = mid;   
    int maybeResultToLeft = firstOccur(A, x, first, mid-1);
    if (maybeResultToLeft == -1) {
       return result;
    }
    return maybeResultToLeft;
}

或者一句单行

return maybeResultToLeft == -1? result : maybeResultToLeft;

我们需要选择当前 (x) 元素左侧的元素 (x)(如果存在 - maybeResultToLeft != -1)