Please explain me how the binarySearch method works normally and also in the below program?
import java.utils.Arrays.*;
public class BinarySearch
{
public static final int NOT_FOUND = -1;
/**
* Performs the standard binary search
* using two comparisons per level.
* @return index where item is found, or NOT_FOUND.
*/
public static int binarySearch( Comparable [ ] a, Comparable x )
{
int low = 0;
int high = a.length - 1;
int mid;
while( low <= high )
{
mid = ( low + high ) / 2;
if( a[ mid ].compareTo( x ) < 0 )
low = mid + 1;
else if( a[ mid ].compareTo( x ) > 0 )
high = mid - 1;
else
return mid;
}
return NOT_FOUND; // NOT_FOUND = -1
}
//
Test program
public static void main(
String [ ] args )
{
int SIZE = 8;
Comparable [ ] a = new Integer [ SIZE ];
for( int i = 0; i < SIZE; i++ )
a[ i ] = new Integer( i * 2 );
for( int i = 0; i < SIZE * 2; i++ )
System.out.println( "Found " + i + " at " +
binarySearch( a, new Integer( i ) ) );
}
}
The output is :
Found 0 at 0
Found 1 at -1
Found 2 at 1
Found 3 at -1
Found 4 at 2
Found 5 at -1
Found 6 at 3
Found 7 at -1
Found 8 at 4
Found 9 at -1
Found 10 at 5
Found 11 at -1
Found 12 at 6
Found 13 at -1
Found 14 at 7
Found 15 at -1
Please help me out with this, i am preparing for scjp exam and stuck with this method. I am really confused how a binarySearch() method works in Java, please explain me in detail