// Stuart Reges
// 1/11/08
//
// This class provides a binarySearch method for searching a sorted array of
// ints.

public class Arrays {
	// pre : elements in indexes fromIndex (inclusive) to toIndex (exclusive)
	//	   are in sorted (nondecreasing) order
	// post: returns the index of the given key in the list within the range
	//	   fromIndex (inclusive) through toIndex(exclusive); returns
	//	   (-(insertion point) - 1) otherwise.  The insertion point is
	//	   defined as the point at which the key would be inserted into the
	//	   array: the index of the first element in the range greater than
	//	   the key, or toIndex if all elements in the range are less than the
	//	   specified key.  Note that this guarantees that the return value
	//	   will be >= 0 if and only if the key is found.  If the list
	//	   contains multiple copies of the key in the given range, there is
	//	   no guarantee which index is returned.
	public static int binarySearch(int[] list, int fromIndex, int toIndex,
								   int key) {
		int low = fromIndex;
		int high = toIndex - 1;
	
		while (low <= high) {
			int mid = (low + high) / 2;
			int midVal = list[mid];
	
			if (midVal < key)
				low = mid + 1;
			else if (midVal > key)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -(low + 1);  // key not found.
	}
}