CODEWITHSUNDEEP
java
asritha
asritha

Reputation: 9

Wrong result for Binary Search in Java

I am new to programming and wrote this code for recursive binary search, but the output is wrong.
I tried debugging it many times but could not know where I am going wrong.

public class Number {
    public static void main (String[] args){
        int []a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
        int key = 7;
        int mid,low,high;
        low=0;
        high=a.length-1;
        int pos=binarySearch(a,key,low,high);
        System.out.println(key +" is found at "+pos+" position");
    }

    public static int binarySearch(int[]a,int key,int low, int high) {

        int mid=(low+high)/2;

        if(key<a[mid]){
            high=mid-1;
            binarySearch(a,key,low,high);
        }
        else if(key >a[mid]){
            low=mid+1;
            binarySearch(a,key,low,high);
        }
        else if(low>high){
            return -1;
        }
        return mid;
    }
}

Upvotes: 0

Views: 63

Answers (3)

Filip Bulovic
Filip Bulovic

Reputation: 1816

During recursive calls execution of caller is interrupted and his execution frame is pushed onto stack. When callee finishes execution callers frame is retrieved from the stack and his execution proceeds. You assigned 9 to mid and you returned mid without reassigning it. If you try different size arrays you will see that always initial mid is returned and all recursive calls are made for no reason. To debug place one System.out.println("returning "+mid); in front of return statement.

Upvotes: 2

Siphor
Siphor

Reputation: 2544

//ignores found value
binarySearch(a,key,low,high);

should be

//returns value
return binarySearch(a,key,low,high);

in both "if" and "else if" clause

Upvotes: 1

wingsareuponus
wingsareuponus

Reputation: 15

You should first check if mid equals key. If it does, escape.

Upvotes: 0

Related Questions