public class BasicSearch {

	public static int linearSearch(int [] data, int key) 
	{
		int locatedAt = -1;				// Initialize to not found indicator

		for( int k = 0; k < data.length; ++ k) 
		{
			if( key == data[k]) 
			{
				locatedAt = k;
				break;
			}
		}
		return locatedAt;
	}

	public static int linearSearch(int [] data, int ndata, int key) 
	{
		int locatedAt = -1;				// Initialize to not found indicator

		for( int k = 0; k < ndata; ++ k) 
		{
			if( key == data[k]) 
			{
				locatedAt = k;
				break;
			}
		}
		return locatedAt;
	}

	public static int linearSearch(int [] data, int startIndex, int ndata, int key) 
	{
		int locatedAt = -1;				// Initialize to not found indicator

		for( int k = 0; k < ndata; ++ k) 
		{
			if( key == data[startIndex + k]) 
			{
				locatedAt = startIndex + k;
				break;
			}
		}
		return locatedAt;
	}
	
	public static int binarySearch( int [] data, int key ) 
	{
		int locatedAt = -1;				// Initialize to not found indicator
		int low = 0;
		int high = data.length - 1;

		while( low <= high ) 
		{
			int mid = (low + high) / 2;
			if( key > data[mid] ) 
				low = mid + 1;			// key may be in the upper half
			else if( key < data[mid] ) 
				high = mid - 1;			// key may be in the lower half
			else
			{
				locatedAt = mid;
				break;
			}
		}
		return locatedAt;
	}
	
	public static int binarySearch( int [] data, int ndata, int key ) 
	{
		int locatedAt = -1;				// Initialize to not found indicator
		int low = 0;
		int high = ndata - 1;

		while( low <= high ) 
		{
			int mid = (low + high) / 2;
			if( key > data[mid] ) 
				low = mid + 1;			// key may be in the upper half
			else if( key < data[mid] ) 
				high = mid - 1;			// key may be in the lower half
			else
			{
				locatedAt = mid;
				break;
			}
		}
		return locatedAt;
	}

	public static int recursiveBinarySearch( int [] data, int key ) 
	{
		return recursiveBinarySearch( data, 0, data.length -1, key );
	}

	public static int recursiveBinarySearch( int [] data, int ndata,  int key ) 
	{
		return recursiveBinarySearch( data, 0, ndata - 1, key );
	}
	
	private static int recursiveBinarySearch( int [] data, int low, int high, int key) 
	{
		   if( low <= high ) 
		   {
		       int mid = ( low + high ) / 2;
		       if( key == data[mid] ) 
		           return mid;				// found the key.
		       else if( key < data[mid] )
		           return recursiveBinarySearch( data, low, mid - 1, key);
		       else
		           return recursiveBinarySearch( data, mid + 1, high, key);
		   }
		   return -1;			// key not found
		}
}