Generic binary search Java

I've been trying to make this code work. I have to create a generic binary version of the binary search. I'm not sure how to compare two generic types without the comparable interface

import java.util.ArrayList; 

public class BinarySearcher<T> {
    private T[] a;

    public BinarySearcher(T[] words) {
        a = words;
    }

    public int search(T v) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            T midVal = a[mid];  

            if (v.compareTo(midVal) < 0) {
                low = mid - 1;
            }   

            else if (v.compareTo(midVal) > 0) {
                high = mid  + 1; 
            }
        }

  开发者_JAVA百科      return -1;
    }

    public int compareTo(T a) {
        return this.value.compare - b;
    }
}

This is the tester class:

import java.util.Arrays;
import java.util.Scanner;
/**
  This program tests the binary search algorithm.
*/
public class BinarySearchTester {
    public static void main(String[] args) {
        String[] words = {"Alpha", "Bravo", "Charlie", "Delta", "Echo", 
            "Foxtrot", "Golf", "Hotel", "India", "Juliet", "Kilo", "Lima", 
            "Mike", "November", "Oscar", "Papa", "Quebec", "Romeo", 
            "Sierra", "Tango", "Uniform", "Victor", "Whiskey", "X-Ray", 
            "Yankee", "Zulu"};
        BinarySearcher<String> searcher = new BinarySearcher<String>(words);
        System.out.println(searcher.search("November"));
        System.out.println("Expected: 13");
        System.out.println(searcher.search("October"));
        System.out.println("Expected: -1");
    }
}

public class BinarySearcher<T extends Comparable<T>> { ...

This'll allow your BinarySearcher to work for everything that can be compared with compareTo, which should be generic enough.

There's no way that your generic method can compare two instances of some arbitrary type T, without having any constraints on T or having information some other way about how to compare two Ts.

You have a few choices:

Add a constraint to T:

public class BinarySearcher<T extends Comparable<T>>

Or pass in a Comparator<T> to your search method that can be called to do the comparison:

public int search(T v, Comparator<T> comp) {
    // ...
    if (comp.compare(v, midVal < 0)) {
    // ...
}

Side note: I would avoid calling compareTo two times in your search method; you don't know if comparing the two objects is expensive. Instead of this:

if (v.compareTo(midVal) < 0) {
    low = mid - 1;
}   
else if (v.compareTo(midVal) > 0) {
    high = mid  + 1; 
}

Do something like this:

int result = v.compareTo(midVal);
if (result < 0) {
    low = mid - 1;
}   
else if (result > 0) {
    high = mid  + 1; 
}

Even after doing all the changes suggested above, the Conditions you are using are incorrect (your changing of low and high pointers) and you need an else clause after else if to return the index.

public class BinarySearcher<T extends Comparable<T>> {
    private T[] a;

    public BinarySearcher(T[] words) {
        a = words;
    }

    public int search(Comparable<T> v) {
        int low = 0;
        int high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            T midVal = a[mid];
            int result = v.compareTo(midVal);

            if (result < 0) {
                high = mid - 1;
            }

            else if (result > 0) {
                low = mid + 1;
            } 

            else {
                return mid;
            }
        }

        return -1;
    }
}

It is impossible to compare types that do not implement Comparable interface. Not by using compareTo().

Try this:

class BinarySearcher<T extends Comparable<T>>

As the others already mentioned leting T extends Comparable would solve your issue. Buuuut why are you reinventing the wheel? You could easily use the existing generic Java Binary Search:

System.out.println(Arrays.binarySearch(words, "November", null));

Note that if null is passed as comparable parameter, the natural element order is taken!

Enjoy!

@Erik's answer shows how to modify your code so that it requires that the parameter type T is comparable.

The other alternative is to use a Comparator<T>; e.g.

import java.util.ArrayList; 

public class BinarySearcher<T> {

    private T[] a;
    private Comparator<T> c;

    public BinarySearcher(T[] words, Comparator<T> comparator) {
        a = words;
        c = comparator;
    }

    public int search(T v) {
        int low = 0;
        int high = a.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            T midVal = a[mid];  
            if (c.compare(v, midVal) < 0) {
                low = mid - 1;
            }   
            else if (c.compare(v, midVal) > 0) {
                high = mid  + 1; 
            }
        }
        return -1;
    }
}

You could combine the two approaches by modifying the original constructor to use a comparator that casts the first values it wants to compare to Comparable instances. This will probably doing an unsafe conversion, and will result in a ClassCastException if the actual type corresponding to T is not actually a Comparable.

From a design perspective, it would be a better idea if the BinarySearcher constructor either checked that words was sorted, or sorted the array itself. Binary search will give the wrong answer if words is not properly ordered.

The following class can be used do to binary search for any data type.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class GenericBinarySearch{

    private int midPoint(int iMin, int iMax){
        return iMin + (iMax - iMin)/2;
    }

    public <T> int search(List<T> list, T Key, int iMin, int iMax, Comparator<T> comparator){
        if(list == null || list.size() == 0){
            return -1;
        }
        int iMid = midPoint(iMin, iMax);
        if(iMid > iMax || iMid < iMin){
            return -1;
        }
        if(comparator.compare(list.get(iMid), Key) > 0){
            return search(list, Key, iMin, iMid-1, comparator);
        }else if(comparator.compare(list.get(iMid), Key) < 0){
            return search(list, Key, iMid+1, iMax, comparator);
        }else{
            return iMid;
        }
    }

    public static void main(String[] args) {
        GenericBinarySearch bs = new GenericBinarySearch();
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        int key = 2;
        int iMin = 0;
        int iMax = list.size()-1;

        //Java 8 - Lambda expressions 
        // new Comparator( public T int compare(T o1, T o2) {
        //      return o1.compareTo(o2);
        // }) ---> same expression is replaced by 
        // (T o1, T o2) -> o1.compareTo(o2) or (o1,o2) -> o1.compareTo(o2)   
        int index = bs.search(list, key, iMin, iMax, (o1,o2) -> o1.compareTo(o2));
        System.out.println(index);
    }


}