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