searches.java

国外的数据结构与算法分析用书

public class Searches 
{
	/**	The index of the first occurrence of key in array (-1 if it doesn't exist).
		Analysis : Time = O(n), n = length of the array */
	public static int linSearch(short[] array, short key)
	{
		for (int i = 0; i < array.length; i++)
			if (array[i] == key)
				return i;
		return -1;
	}

	/**	The index of the first occurrence of Object `key' in `array' (-1 if it doesn't exist).
		Analysis : Time = O(n), n = length of the array */
	public static int linSearch(Object[ ] array, Object key)
	{
		for (int i = 0; i < array.length; i++)
			if (array[i].equals(key))
				return i;
		return -1;
	}

	/**	The index of the first occurrence of key in array (-1 if it doesn't exist).
		Analysis : Time = O(log n), where n = length of the array */
	public static int binarySearch(short array[], int key)
	{
		int low = 0, high = array.length - 1;
		boolean found = false;
		while (low <= high)
		{
			int middle = (low + high) / 2;
			if (key == array[middle])
				return middle;
			else if (key < array[middle])
				high = middle - 1;
			else
				low = middle + 1;
		}
		return -1;
	}
}