CS3343/3341
 Analysis of Algorithms 
Spring 2012
  Binary Search   

Binary Search Algorithm

This is the standard binary search algorithm that you've studied in CS1713 and CS2123. [See Exercise 2.3-5, page 39 (3rd Ed.) and page 37(2nd Ed.).] Normally this would be written in Java as a generic class for any Comparable items, rather than just int. Similarly, there are old-fashioned methods to do generics in C (K & R C, page 120), but now any C generics should be done in C++. We are trying to study basic algorithms without distracting details.

The algorithm searches a sorted array of values. It starts with array indexes low and high giving the range to search. mid is calculated at the midpoint between these two indexes. The item searched for is either at mid (and we're done), or below or above mid. In either case we can cut the range of the search in half. The halving process continues until we either find the item searched for or know that it is missing.

We are searching an array of n elements. At each stage we divide the search range in two until we succeed. This process of repeatedly dividing an integer by 2 is common. It takes log2n steps, so the binary search algorithm runs in time Θ(log2n).

In terms of recurrences, which your text emphasizes, if T(n) is the time to search n elements, then the recurrence should be:

where c is a constant independent of n. Then the recursion tree of this recurrence [See 3rd Ed., pages 37-38] is just a stack of at most log2n levels, each a cost of at most c, so the total cost of execution time is at most c*log2n, that is, T(n) is Θ(log2n). Finally recall that these asymptotic bounds include an implied constant, so it doesn't matter what the base of the logarithm is, and we can say that T(n) is Θ(log n).

Binary Search in Java and C
// BinarySearch.java: simple implementation
public class BinarySearch {

   public int binarySearch(int[] x, int y) {
      int low = 0;
      int high = x.length - 1;
      while (low <= high) {
         int mid = (low + high)/2;
         if (x[mid] == y) return mid; // found
         else if (x[mid] < y) low = mid + 1;
         else high = mid - 1;
      }
      return -1; // not found
   }

   public static void main(String[] args) {
      BinarySearch bin = new BinarySearch();
      int[] a =
        { 2, 8,12,14,16,19,24,28,31,33,// 0-9
         39,40,45,49,51,53,54,56,57,60,// 10-19
         63,69,77,82,88,89,94,96,99};  // 20-28

      for (int i = 0; i < a.length; i++)
         System.out.print(bin.binarySearch(a,
            a[i]) + " ");         
      System.out.print(bin.binarySearch(a,1)  + " ");
      System.out.print(bin.binarySearch(a,100)+ " ");
      System.out.print(bin.binarySearch(a,17) + " ");
      System.out.print(bin.binarySearch(a,42) + " ");
      System.out.print(bin.binarySearch(a,97) + " ");
      System.out.println();
   }
}


// binsearch.c: simple implementation
#include <stdio.h>

int binarysearch(int len, int x[], int y) {
   int low = 0;
   int high = len - 1;
   while (low <= high) {
      int mid = (low + high) / 2;
      if (x[mid] == y) return mid; // found
      else if (x[mid] < y) low = mid + 1;
      else high = mid - 1;
   }
   return -1; // not found
}

int main() {

   int a[] =
    { 2, 8,12,14,16,19,24,28,31,33,// 0-9
     39,40,45,49,51,53,54,56,57,60,// 10-19
     63,69,77,82,88,89,94,96,99};  // 20-28
   int i;
   for (i = 0; i < 29; i++)
      printf("%i ", binarysearch(29, a, a[i]));

   printf("%i ", binarysearch(29, a,1));
   printf("%i ", binarysearch(29, a,100));
   printf("%i ", binarysearch(29, a,17));
   printf("%i ", binarysearch(29, a,42));
   printf("%i ", binarysearch(29, a,97));
   printf("\n");
}

Common Output (all array indexes in A, or the error code -1):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 -1 -1 -1 -1 -1

Revision date: 2011-10-28. (Please use ISO 8601, the International Standard Date and Time Notation.)