CODEWITHSUNDEEP
javasortingrecursion
mendy
mendy

Reputation: 191

Finding first occurence of number in a SORTED array recursively

I would like to find the first occurence of a given number x in a sorted array. This is the method I have so far:

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));

}

When I run the code, the function works for numbers 1 & 5 and anything added. Unfortunately, when submitting x=2, it returns index 2, which is not true. Am I missing a small detail?

Upvotes: 0

Views: 477

Answers (1)

Thiyagu
Thiyagu

Reputation: 17890

You are not considering the return value of the recursive function here

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

Change it to 

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

Or a one-liner

return maybeResultToLeft == -1? result : maybeResultToLeft;

We need to pick the element (x) to the left of the current (x) element (if it exists - maybeResultToLeft != -1)

Upvotes: 3

Related Questions