Binary search

Binary search or half-interval search is a fast search algorithm to find the position of a target value in a sorted array. The run-time complexity of this algorithm is Ο(log n).

Binary search
Binary search

In binary search, the target value is compared to the middle element of the array; if they are not equal, the half of array which target can not lie, is eliminated and the search continues in the remaining half until it is successful.

1. Algorithm

  1. Set L to 0 and R to n − 1.
  2. If L > R, the search terminates as unsuccessful.
  3. Set m (the position of the middle element) to the floor of (L + R) / 2.
  4. If A[m] < T(target value), set L to (m + 1) and go to step 2. If A[m] > T, set R to (m – 1) and go to step 2.
  5. Now Am = T, the search is done; return m.

2. Java code

/**
 * Array should be sorted asc
 * The implementation is not recursive
 * Complexity of the algorithm
 * Best: O(1)
 * Worst: O(logn)
 */
 public static int binarySearch(int[] array, int val){
     int low = 0;
     int high = array.length - 1;
     while(low < high){
         int mid = (high + low) / 2;
         if(array[mid] == val)
             return mid;
         else if(array[mid] < val)
             low = mid +1;
         else
             high = mid - 1;
     }
     return -1;
 }

2.1. Recursive implementation

/**
 * Array should be sorted asc
 * The implementation is recursive
 * Complexity of the algorithm
 * Best: O(1)
 * Worst: O(log n)
 */
 public static int binarySearch(int[] array, int val, int low, int high){
     int mid = (high + low) / 2;
     if(high < low)
         return -1;
     if(array[mid] == val)
         return mid;
     else if(array[mid] < val)
         return binarySearch(array, val,mid + 1, high);
     else
         return binarySearch(array,val,low ,mid - 1);
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s