Binary Search

We have seen quite a number of articles on this site that discussed various sorting techniques. So, How can we take advantage of sorted data?. Sorting the data helps with quite a number of operations, like

1. Finding the minimum - Complexity 0(1) - just pick array[0]
2. Finding the maximum - Complexity 0(1) - just pick array[n - 1], since array index starts at 0
3. Finding 'k' the smallest element - Complexity 0(1) - just pick array[k - 1], since array index starts at 0
4. Finding 'k' the largest element  Complexity 0(1) - just pick array[n - k - 1], since array index starts at 0
5. Searching for a element - Complexity O(log n) 

If we are going to, frequently do the any of above operations, it makes sense to pay the cost O(n * log n) associated with sorting and have the data sorted, so that, all the subsequent operation becomes cheaper. In this article we'll try to dive deep into the binary search algorithm. Note, that binary search works on sorted arrays.

Linear Search

For the sake of completeness, let's quickly implement a linear search algorithm. The complexity of the below code is O(n), since it visits all the elements in the array. The below code works in both the cases i.e it works for the case if the array is not sorted as well as for the case when the array is sorted.

  public static int linearSearch(int[] array, int key) {
    for (int i = 0; i < array.length; i++) {
      if (array[i] == key) {
        return i;
      }
    }

    return -1; //Not found
  }

Binary Search

In the above linear search code, we were not taking advantage of the fact, if the array is sorted, we can search faster.

So, how does binary search work ?, say we are given an array and an element called 'key' - We need to find, if this element exists in the array. Binary search takes advantage of the fact that the array is sorted.

Given an input array like below, and a value to search called 'key', say key = 11

1. We look into the middle of the array, if the middle of the array is our key - We got lucky, we say we found the element, otherwise.
2. If the given key is less than the value in the middle of the array - then the element we are looking for should be in the lower part of the array.
3. If the given key is greater than the value in the middle of the array - then the element we are looking for should be in the upper part of the array.

Essentially, what we are doing is that at each step the number of elements, we need to search reduces by half as shown below. So the complexity reduces to O(log n), since every step halves the search space (or the number of elements that we need to search).

Here is the pictorial representation of the step by step execution of the algorithm for the given sample array and the key.

Step 1 : Find the middle element, the below picture shows all the indexes used in the code, 'lowerIndex' is at the start of the array, 'upperIndex' is at the end of the array and 'mid' in the middle of the array

Step 2 : Now compare the 'mid' value to key (11 in our case). Since key > array[mid] - We can throw away the first half of the array, now our search space has become half the original elements. All elements we can throw are crossed out in the below picture

Step 3 : The below picture shows after we have thrown away the first half of array - We have also moved the 'lowerIndex' up,  eliminating the first half of the array all elements, including the previous 'mid' is eliminated. Now again we calculate a new 'mid', which is as shown below

Step 4 : Again key > array[mid], So we throw another half of the array elements. Now the pic below shows a new 'mid' after we eliminated another half of elements.

Step 5 : Again key > array[mid], So we throw another half of the array elements. Now the pic below shows a new 'mid' after we eliminated another half of elements. So we have finally found the key which is 11. Hence we return the index of 11 as an answer.

Iterative binary search implementation

Here an iterative implementation of the binary search algorithm. Its quite simple as explained in the above text

1. find the middle element, if it is the value, we are searching for, return it immediately.
2. else imagine the array is split into two, we now either search the lower part of array i.e [lowerIndex to mid - 1]  or 
3. search the upper part of array [mid + 1 to  upperIndex ] - so we adjust the index variables accordingly.

  public static int iterativeBinarySearch(int[] array, int key) {
    int lowerIndex = 0;
    int upperIndex = array.length - 1;

    while (lowerIndex <= upperIndex) {
      int mid = (lowerIndex + upperIndex) / 2;

      if (key == array[mid]) {
        return mid;
      } else if (key < array[mid]) {
        upperIndex = mid - 1;
      } else {

        lowerIndex = mid + 1;
      }

    }
    return -1; //Not found
  }

Recursive binary search implementation

Here is a recursive implementation of the same algorithm.  It uses a wrapper method so that user/consumer of the binary search method, need not give additional parameters like lowerIndex and upperIndex.

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

  // Internal private method
  private static int recursiveBinarySearch(int[] array, int key,
          int lowerIndex, int upperIndex) {
    if (lowerIndex > upperIndex) {
      return -1;
    }

    int mid = (lowerIndex + upperIndex) / 2;
    if (array[mid] == key) {
      return mid;
    } else if (key < array[mid]) {
      return recursiveBinarySearch(array, key, lowerIndex, mid - 1);
    } else {
      //This is key > array[mid] case;
      return recursiveBinarySearch(array, key, mid + 1, upperIndex);
    }
  }

Binary Search complexity

Complexity of binary search is O(log n), since, at every step we reduce the search/problem space by half. i.e if we had 12 elements in the array, after first iteration, we need to search only 6 elements in the next iteration.

Complete Code

Here is the complete code for your reference.

 
/*
 * Copyright CodenLearn.com
 *
 * License : http://www.apache.org/licenses/LICENSE-2.0
 *
 * This class has 2 implementations of binary search both iterative and 
 * recursive versions
 *
 *  Complexity: O(log n)
 */

import java.util.Arrays;

public class SearchExamples {

  public static int linearSearch(int[] array, int key) {
    for (int i = 0; i < array.length; i++) {
      if (array[i] == key) {
        return i;
      }
    }

    return -1;
  }

  public static int iterativeBinarySearch(int[] array, int key) {
    int lowerIndex = 0;
    int upperIndex = array.length - 1;

    while (lowerIndex <= upperIndex) {
      int mid = (lowerIndex + upperIndex) / 2;

      if (key == array[mid]) {
        return mid;
      } else if (key < array[mid]) {
        upperIndex = mid - 1;
      } else {

        lowerIndex = mid + 1;
      }

    }
    return -1;
  }

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

  private static int recursiveBinarySearch(int[] array, int key,
          int lowerIndex, int upperIndex) {
    if (lowerIndex > upperIndex) {
      return -1;
    }

    int mid = (lowerIndex + upperIndex) / 2;
    if (array[mid] == key) {
      return mid;
    } else if (key < array[mid]) {
      return recursiveBinarySearch(array, key, lowerIndex, mid - 1);
    } else {
      //This is key > array[mid] case;
      return recursiveBinarySearch(array, key, mid + 1, upperIndex);
    }
  }

  /*
   * Utility function - Given an array just prints it to output/console
   */
  public static void dumpArray(int array[]) {

    StringBuilder output = new StringBuilder();
    for (int value : array) {
      output.append(value).append(",");
    }
    System.out.println("Array as string : " + output);
  }

  public static void main(String args[]) {

    int[] inputArray = {9, 4, 2, 6, 5, 8, 3, 11, 0};

    System.out.println("Raw array (NOT sorted) is : ");
    SearchExamples.dumpArray(inputArray);

    int result = SearchExamples.linearSearch(inputArray, 11);
    System.out.println(" Index of item 11 in array is  : " + result);

    result = SearchExamples.linearSearch(inputArray, 25);
    System.out.println(" Index of item 11 in array is  : " + result);

    // Now working on sorted Array
    // The following method part of JAVA sorts the array using quicksort
    // for primitive datatypes
    Arrays.sort(inputArray);

    System.out.println("\n\nSorted array is  : ");
    SearchExamples.dumpArray(inputArray);

    result = SearchExamples.iterativeBinarySearch(inputArray, 11);
    System.out.println(" Index of item 11 in SORTED ARRAY is - using iterative binary Search : " + result);

    result = SearchExamples.iterativeBinarySearch(inputArray, 25);
    System.out.println(" Index of item 25 in SORTED ARRAY is - using iterative binary Search :   : " + result);

    result = SearchExamples.binarySearch(inputArray, 11);
    System.out.println(" Index of item 11 in SORTED ARRAY is - using recursive binary Search : " + result);

    result = SearchExamples.binarySearch(inputArray, 25);
    System.out.println(" Index of item 25 in SORTED ARRAY is - using recursive binary Search :   : " + result);
  }
}