CODEWITHSUNDEEP
javaarraysrecursion
Jen123
Jen123

Reputation: 49

Binary Search using recursion java

I am trying to write a method where I can find the index of the desired number using binary search and recursion only. This is the method that I wrote:

public static int binSearch_r (int[] data, int value, int from, int to)
    {
        if (from <= to)
        {
            int middle = (from+to)/2;
            if (data[middle] > value)
            {
                binSearch_r(data, value, from, middle - 1);
            }
            else if (data[middle] < value)
            {
                binSearch_r(data, value, middle+1, to);
            }
            else
            {
                return middle;
            }
        }
        return -1;
    }

data is the original array that is inputed, value is the number I am trying to find, from is the left most index of the array and to is the right most index of the array.

The array that I tested this method with is simply {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. However, when I set value to 9, the initial "from" to 0 and the initial "to" to array.length-1, I receive -1 instead of the desired index. This happens for any number that I set for value. What am I doing wrong?

Upvotes: 3

Views: 2769

Answers (2)

Praneet Negi
Praneet Negi

Reputation: 1

def bs(array,target_value,i,j):
    # here i is initial postion and j is last position of array 
    mid=(i+j)//2
    if array[mid]==target_value:
        return mid
    if array[mid]>target_value:
         j=mid-1
         return bs(array,target_value,i,j)
         
    if array[mid]<target_value:
        i=mid+1
        return bs(array,target_value,i,j)



array=[1,2,3,4,5,6,7]
x=bs(array,7,0,7)
print(x)

Upvotes: 0

Zachary
Zachary

Reputation: 1703

If you are unfamiliar with recursion, this is a great resource that explains it well within a Java context.

In a recursive binary search, the recursive method will reduce the search space if it cannot find the correct index. With the reduced search space the method will call itself to find the index within this reduced space. Each recursive call expects a value to be returned.

public static int binSearch_r (int[] data, int value, int from, int to) {
    if (from <= to) {
        int middle = (from+to)/2;

        if (data[middle] > value) {
            return binSearch_r(data, value, from, middle - 1);
        } else if (data[middle] < value) {
            return binSearch_r(data, value, middle+1, to);
        }
        return middle;            
    }
    return -1;
}

(Shifted from comment to answer question)

Upvotes: 3

Related Questions