CODEWITHSUNDEEP
javaalgorithmbinary-search
damon
damon

Reputation: 8477

lo,hi indices in recursive binarysearch in java

For a classic binarySearch on an array of java Strings (say String[] a), which is the correct way of calling the search method? is it 

binarySearch(a,key,0,a.length)

or

binarySearch(a,key,0,a.length-1)

I tried both for the below implementation,and both seems to work.. Is there a usecase where either of these calls can fail?

class BS{
    public static int binarySearch(String[] a,String key){
        return binarySearch(a,key,0,a.length);
        //return binarySearch(a,key,0,a.length-1);
    }
    public static int binarySearch(String[] a,String key,int lo,int hi)   {
        if(lo > hi){
            return -1;
        }
        int mid = lo + (hi - lo)/2;
        if(less(key,a[mid])){
            return binarySearch(a,key,lo,mid-1);
        }
        else if(less(a[mid],key)){
            return binarySearch(a,key,mid+1,hi);
        }
        else{
            return mid;
        }

    }
    private static boolean less(String x,String y){
        return x.compareTo(y) < 0;
    }
     public static void main(String[] args) {
        String[] a = {"D","E","F","M","K","I"};
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
        int x =  binarySearch(a,"M");
        System.out.println("found at :"+x);

     }
}

Upvotes: 1

Views: 388

Answers (2)

Lake
Lake

Reputation: 4092

Consider the case where

a = [ "foo" ]

and you search key "zoo" with binarySearch(a,key,0,a.length);

The code will search for it in interval[0,1], see it should be right than that, next recursion searches interval [1,1], causing an indexing of a[1] at line 

if(less(key,a[mid])){

resulting in a array out of bounds error.

The second solution will work fine.

Upvotes: 1

MD Sayem Ahmed
MD Sayem Ahmed

Reputation: 29166

I think the second approach will be safe.

Consider this case - you have an array of 9 elements and the key is situated at the last index (8-th element). Then you might have a method call like this if you follow the first approach - 

binarySearch(a, key, 9, 9);

Now, in that method execution, the integer division in the following line will result in 9 - 

int mid = 9 + (9 - 9)/2;

and you will be indexing your array with 9 in the next line - 

if( less(key,a[mid]) ) { // You'll face ArrayIndexOutOfBoundException
    ....
}

which will be invalid and cause ArrayIndexOutOfBoundException.

The second approach however will be just fine.

Upvotes: 1

Related Questions