Поиск первого вхождения числа в массив SORTED рекурсивно

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 and anything added.К сожалению, при отправке 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)