package cusack.algorithms.util;
import java.util.List;
public class SearchUtilities {
/**
* The binary search algorithm. Should be called with first=0 and last=size-1 the first time.
*
* @param list the list to search
* @param first the index of the first element in the array to consider
* @param last the index of the last element in the array to consider
* @param value the value you are trying to find
* @return true if and only if value is in the array between the first and the last elements, inclusive.
*/
public static boolean binarySearch(int[] list, int first, int last, int value) {
if (last >= first) {
int mid = (last + first) / 2;
if (value == list[mid]) {
return true;
} else if (value < list[mid]) {
return binarySearch(list, first, mid - 1, value);
} else { // Then (value > list[mid])
return binarySearch(list, mid + 1, last, value);
}
} else {
return false;
}
}
/**
* The binary search algorithm. Should be called with first=0 and last=size-1 the first time. List list should be a
* list of Comparable objects, all the same type as the value. Unfortunately, I don't think there is any way to
* enforce this in Java.
*
* @param list the list to search
* @param first the index of the first element in the array to consider
* @param last the index of the last element in the array to consider
* @param value the value you are trying to find
* @return true if and only if value is in the array between the first and the last elements, inclusive.
*/
public static boolean binarySearch(List<?> list, int first, int last, Comparable value) {
if (last >= first) {
int mid = (last + first) / 2;
if (value.compareTo(list.get(mid)) == 0) {
return true;
} else if (value.compareTo(list.get(mid)) < 0) {
return binarySearch(list, first, mid - 1, value);
} else {
return binarySearch(list, mid + 1, last, value);
}
} else {
return false;
}
}
/**
* The binary search algorithm. Should be called with first=0 and last=size-1 the first time.
*
* @param list the list to search
* @param first the index of the first element in the array to consider
* @param last the index of the last element in the array to consider
* @param value the value you are trying to find
* @return true if and only if value is in the array between the first and the last elements, inclusive.
*/
public static boolean binarySearch(Comparable[] list, int first, int last, Comparable value) {
if (last >= first) {
int mid = (last + first) / 2;
if (value.compareTo(list[mid]) == 0) {
return true;
} else if (value.compareTo(list[mid]) < 0) {
return binarySearch(list, first, mid - 1, value);
} else {
return binarySearch(list, mid + 1, last, value);
}
} else {
return false;
}
}
}