Overview

Binary Search is a commonly used search algorithm in programming. Let’s see how we implement it by using the Java programming language.

For binary search to work, we need to make sure the list is sorted first, let’s say, in ascending order.

These are the procedures for binary search:

1. If the key is less than the middle element, you need to continue to search for the key only in the first half of the array.
2. If the key is equal to the middle element, the search ends with a match.
3. If the key is greater than the middle element, you need to continue to search for the key only in the second half of the array.

Time complexity

Obviously, after each comparison eliminates at least half of the array. Suppose the array has n elements and sometimes you eliminate half of the array sometimes you eliminate half plus one.

For convenience, let n be a power of 2. After the first comparison, n/2 elements are left for further search; after the second comparison, \dfrac {\left( \dfrac {n}{2}\right) }{2} elements are left. After the k th comparison, \dfrac {n}{2^{k}} elements are left for further search. When k = \log 2^{n}, only one element is left in the array, and you need only one more comparison. Therefore, in the worst case when using the binary search approach, you need \log 2^{n+1} comparisons to find an element in the sorted array. In the worst case for a list of 1024 (2^{10} ) elements, binary search requires only 11 comparisons, whereas a linear search requires 1023 comparisons in the worst case.

The portion of the array being searched shrinks by half after each comparison. Let low and high denote, respectively, the first index and last index of the array that is currently being searched. Initially, low is 0 and high is list.length − 1 . Let mid denote the index of the middle element, so mid is \dfrac {\left( low+high\right) }{2}. Figure below shows how to find key 11 in the list {2 , 4 , 7 , 10 , 11 , 45 , 50 , 59 , 60 , 66 , 69 , 70 , 79 } using binary search.

Implement it using Java

You now know how things work. The next Step is to implement it by using Java. Don’t rush to give a complete solution all at once.

Implement is incrementally,one step at a time.

1. Finish the first iteration of the search as fixture A shows you. It compares the key with the middle element in the list whose low index is 0 and high index is list.length −1 . If key < list[mid] , set the high index to mid − 1 ; if key == list[mid] , a match is found and return mid ; if key > list[mid] , set the low index to mid + 1 .

2. Consider implementing the method to perform the search repeatedly by adding a loop as fixture B shows you

When the search key is not found then -1 would be returned. But would it be better we return the position where the key should be inserted? In order to do so, we only need to return -low-1 since this stands for the location where the search key should be inserted. Can we simply return -low? No, because if the list has only one element it will return 0 this indicates the key matches list[0] but this is wrong. In a nutshell, returning −low − 1 indicates not only that the key is not in the list, but also where the key would be inserted.

The complete program is given below:

public class BinarySearch {
  /** Use binary search to find the key in the list */
  public static int binarySearch(int[] list, int key) {
    int low = 0;
    int high = list.length - 1;

    while (high >= low) {
      int mid = (low + high) / 2;
      if (key < list[mid])
        high = mid - 1;
      else if (key == list[mid])
        return mid;
      else
        low = mid + 1;
    }

    return -low - 1; // Now high < low
  }
}

The binary search returns the index of the search key if it is contained in the list (line 2) otherwise it will return -low-1(line 17) as the position where the search key should be inserted.

What would happen if we replaced (high >= low) in line 7 with (high > low )? The search would miss a possible matching element. Consider a list with just one element. The search would miss the element.

Does the method still work if there are duplicate elements in the list? Yes, as long as the elements are sorted in increasing order. The method returns the index of one of the matching elements if the element is in the list.

The precondition for the binary search method is that the list must be sorted in increasing order. The postcondition is that the method returns the index of the element that matches the key if the key is in the list or a negative integer k such that −k - 1 is the position for inserting the key.

Let’s see some concret examples for better understanding:

int[] list = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
int i = BinarySearch.binarySearch(list, 2); // Returns 0
int j = BinarySearch.binarySearch(list, 11); // Returns 4
int k = BinarySearch.binarySearch(list, 12); // Returns –6
int l = BinarySearch.binarySearch(list, 1); // Returns –1
int m = BinarySearch.binarySearch(list, 3); // Returns –2

Here is the table that lists the low and high values when the method exits and the value returned from invoking the method.