1 
    public static int binarySearch(double[] arr, int low, int high, double inq){
    int mid = (low + high)/2;
    if(arr == null) return -1;
    if(low > high) return -1;
    if(arr[(int)inq] < arr[low])
    return -1;
    if(arr[(int)inq] > arr[high])
    return -1;
}

I am suppose to search through the array arr recursively to find the index of inq. All I have is the termination cases. Not sure how to go about this problem.

The original question is this one:

search the array slice arr[low:high] for an occurrence of inq. If inq occurs in arr, return an index i such that arr[i] == inq. Otherwise, return -1. Assume that arr is sorted in increasing order.

And these are the answers to some cases:

The input array is table = { 2, 4, 6, 8, 10, 12, 14 }.

  • 2 was found in table[0:6] at index 0
  • 3 was found in table[0:6] at index -1
  • 4 was found in table[2:6] at index -1
  • 12 was found in table[2:5] at index 5

I know how to do it using iterations, but I am new to recursive methods. I'd appreciate any help on this.

Improve this question
1
  • if you know which part you need to search in just ask binarySearch to search in that part. Commented Nov 8, 2015 at 21:10

1 Answer 1

Reset to default
2

The key is to update the search range by updating low and high by passing the modified low and high into the next recursive call. Each call, we update the search range to either [low, mid-1] or [mid+1, high] depending on comparison between inq and arr[mid]

This will work:

public static int binarySearch(double[] arr, int low, int high, double inq){
    int mid = (low + high)/2;
    if(arr == null || low > high) return -1;

    if(arr[mid] == inq) return mid;

    if(arr[mid] < inq) { // inq is in the upper half
        return binarySearch(arr, mid+1, high, inq);
    }
    if(arr[mid] > inq) { // inq is in the lower half
        return binarySearch(arr, low, mid-1, inq);
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

You made this make perfect sense to me. Thanks it works flawlessly.
Glad to help :) Recursion can be hard to wrap heads around in the beginning.
Tell me about it... It is brain wrecking for me to think recursively when iterations are so convenient, but this makes sense to me. So thanks again for the help

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.