A Binary Search

This example implements a binary search, which finds the position of a target value within a sorted array. It compares the target value to the middle element of the array.

If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. 
function binary_search( int A[], int n, int T )
  L = 0
  H = n − 1
  while L ≤ H do
    m = L + floor( ( H - L ) / 2 )
    if A[m] < T
      L = m + 1
    else if A[m] > T
      H = m − 1
    else
      return m
    end if
  end while 
  return unsuccessful
end function

BinarySearch.java (a binary search) 

 // Java program to perform a binary search
 class BinarySearch {

   // The driver method
   public static void main( String args[ ] ) {
     int        n = args.length - 1;
     int array[ ] = new int[ n ];

     // Populate a sorted array.
     for ( int i = 0; i < n; i++ )
       array[i] = Integer.parseInt( args[i] );

     // The element to be searched for
     int element = Integer.parseInt( args[n] );

     // Create an object of BinarySearch class.
     BinarySearch obj = new BinarySearch( );

     // Call the binary search method.
     // Pass arguments: array, element, index of first and last element
     int result = obj.search( array, element, 0, n - 1 );
     if ( result == -1 )
       System.out.println( "Not found" );
     else
       System.out.println( "Element found at index " + result );
   }

   // Binary search in Java
   int search( int array[ ], int element, int low, int high ) {
     // Repeat until the pointers low and high meet each other.
     while ( low <= high ) {
       // Get index of mid element.
       int mid = low + ( high - low ) / 2;

       // If element is less than mid element,
       //   search only the left side of mid.
       if ( array[mid] <  )  low = mid + 1;

       // If element is greater than mid element,
       //   search only the right side of mid.
       else if ( array[mid] >  )  high = mid - 1;

       else return mid;
     }
     return -1;
   }
 }
shell> java BinarySearch  (a list of sorted integers)

(number to be searched for)        




      That’s your best friend and your worst enemy—your own brain.