Observe the Java code given below to understand the binary search algorithm in arrays.
public int binarySearch( int a[], int key )
{
int low = 0;
int high = a.length - 1; //zero based array
int middle;
while( low <= high )
{
middle = ( low + high ) / 2;
if( key == a[ middle ] ) //match
return middle;
else if( key < a[ middle ] )
high = middle - 1; //search low end of array
else
low = middle + 1; //search high end of array
}
return -1; //search key not found
}
We simply start from the middle of the array and check if we have found a match. If not, we check to see if what we've got is greater or lesser than the required value. If it be lesser then we can confidently ignore all the values greater than ( and including ) the mid point. This goes on until we either find a match or when the "low" point is greater than the "high" point.
This algorithm, as must be evident, assumes the array it receives as input to be in a perfectly sorted state, i.e., it works only so long as it is ensured that the array to be searched is in ascending sorted order.