Java general binary search

Question

I tried to get this code to work. I have to create a generic binary version of binary search. I'm not sure how to compare two common types without a 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; } } 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"); } } 

Answer 1

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

This will allow your BinarySearcher to work on everything that can be compared with compareTo , which should be fairly general.

Answer 2

There is no way that your general method can compare two instances of any arbitrary type T without any restrictions on T or have other information on how to compare two T s.

You have several options:

Add a T constraint:

 public class BinarySearcher<T extends Comparable<T>> 

Or go to Comparator<T> to your search method, which can be called for comparison:

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

Side note: I would avoid calling compareTo twice in your search method; You don’t know whether to compare these two objects. 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; } 

Answer 3

Even after making all the changes suggested above, the conditions you use are incorrect (changing low and high pointers), and you need an else condition after else if you 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; } } 

Answer 4

it is not possible to compare types that do not implement the Comparable interface. Not using compareTo() .

Answer 5

Try the following:

 class BinarySearcher<T extends Comparable<T>> 

Answer 6

@Erik's answer shows how to change the code so that it is compatible with the parameter type T

Another alternative is to use Comparator<T> ; eg.

 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 distinguishes the first values ​​that it wants to compare with Comparable instances. This is likely to result in an unsafe conversion and result in a ClassCastException if the actual type matching T is actually not Comparable .

---

From a design point of view, it would be better if the BinarySearcher constructor either checked that the words were sorted or the array itself was sorted. Binary search will give the wrong answer if words incorrectly ordered.

Answer 7

As mentioned above, listing T extends Comparable will help solve your problem. Buuuut, why do you reinvent the wheel? You can easily use existing shared Java binary search:

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

Note that if null is passed as a comparable parameter, the order of the natural elements is executed!

Enjoy it!

Answer 8

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

 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); } }