import java.util.*;
public class Searcher<T> {
// Returns the index of the key in the sorted array, or -1 if the
// key is not found.
public static <T> int binarySearch(T[] array, int arraySize, T key,
Comparator<T> comparer) {
int lowBound = 0;
int highBound = arraySize - 1;
int mid = 0;
//string this.key = key;
while (highBound > lowBound) {
mid = (highBound - lowBound) / 2;
String results = comparer.compare(array[mid], key.toString());
if(results > key){
lowBound = mid + 1;
}
else if(results > key) {
highBound = mid - 1;
}
else { return mid;
}
}
return -1;
}
}
when i run the program I get this error:
Searcher.java:17: error: bad operand types for binary operator '<'
if(results < key){
^
first type: int
second type: T
where T is a type-variable:
For both lines 17 and 20. i cannot for the life of me figure out how to compare the results from line 15 to the key i am searching for in my binary search algorithm.][2]
The result of Comparator::compare is an int, as such you need to change result to be of type int and not String, then you can correct the if else as shown below. a result of 1 indicates that your value is large, 0 is the same, and -1 is less (this depends on how you have implemented the comparator.
import java.util.*;
public class Searcher<T> {
// Returns the index of the key in the sorted array, or -1 if the
// key is not found.
public static <T> int binarySearch(T[] array, int arraySize, T key,
Comparator<T> comparer) {
int lowBound = 0;
int highBound = arraySize - 1;
int mid = 0;
//string this.key = key;
while (highBound > lowBound) {
mid = (highBound - lowBound) / 2;
int results = comparer.compare(array[mid], key);
if(results > 0){
lowBound = mid + 1;
}
else if(results < 0) {
highBound = mid - 1;
}
else { return mid;
}
}
return -1;
}
}
As mentioned in my comment you can have type T implement comparable and then use the Comparable::compareTo method; this would remove the requirement for the Comparator in the method signature.
Example:
public class Searcher<T extends Comparable<T>> {
// Returns the index of the key in the sorted array, or -1 if the
// key is not found.
public int binarySearch(T[] array, int arraySize, T key) {
int lowBound = 0;
int highBound = arraySize - 1;
int mid = 0;
//string this.key = key;
while (highBound > lowBound) {
mid = (highBound - lowBound) / 2;
int results = key.compareTo(array[mid]);
if(results > 0){
lowBound = mid + 1;
}
else if(results < 0) {
highBound = mid - 1;
}
else { return mid;
}
}
return -1;
}
}