CS 3343/3341
  Introduction to Algorithms  
Binary Search
  (With and Without Recursion)  

Binary Search:

The non-recursive binary search on the left is a function you've seen before. It maintains a range between two variables low < high. This range is cut roughly in half at each step of the algorithm. Termination of this algorithm for an unsuccessful search is quite tricky, with low managing to meander over to the right of high, so that low > high and the while loop terminates.

Now consider a recursive version on the right. It maintains the same range as parameters to the function. The very first step is what is always needed in a recursive function: a test of some final condition, to stop the recursion. If instead there were a recursive call at the start, we would go into an "infinite recursive regression," where the program tries to call itself (or call another program) forever. This process terminates when memory runs out.

So the condition if (low > high) return -1; terminates the recursion with the same condition that terminates the while loop in the non-recursive version. If the termination condition is not met, then the recursive version, instead of giving new values to low and high, and then going around the loop, puts these new values into parameters of a recursive call.

When a rercusive call finally returns a value, in general it doesn't return the value directly to the call inside the main function. Instead there will usually be a whole stack of recursive calls, and a corresponding stack of verions of binarySearch that are active (executing) at once. The final call returns a value to the previous call (and terminates that active version of binarySearch), which then returns it to the previous one yet, until finally it is returned into main.

Java Binary Search, With and Without Recursion
// BinarySearch.java: simple implementation
public class BinarySearch {






   // binarySeach: non-recursive
   public int binarySearch(int[] a, int x) {
      int low = 0;
      int high = a.length - 1;
      while (low <= high) {
         int mid = (low + high)/2;
         if (a[mid] == x) return mid;
         else if (a[mid] < x) low = mid + 1;
         else high = mid - 1;
      }
      return -1;
   }

   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,97};  // 20-28
      for (int i = 0; i < a.length; i++)
         System.out.print(bin.binarySearch(a,
            a[i]) + " ");   
      System.out.println();      
      System.out.print(bin.binarySearch(a,1) +" ");
      System.out.print(bin.binarySearch(a,26)+" ");
      System.out.print(bin.binarySearch(a,85)+" ");
      System.out.print(bin.binarySearch(a,99)+" ");
      System.out.println();
   }
}

// BinarySearchRecursive: test a recursive version
public class BinarySearchRecursive {

   // need extra "helper" method, feed in params
   public int binarySearch(int[] a, int x) { 
      return binarySearch(a, x, 0, a.length - 1);
   }
  
   // need extra low and high parameters
   private int binarySearch(int[ ] a, int x,
         int low, int high) {
      if (low > high) return -1; 
      int mid = (low + high)/2;
      if (a[mid] == x) return mid;
      else if (a[mid] < x)
         return binarySearch(a, x, mid+1, high);
      else // last possibility: a[mid] > x
         return binarySearch(a, x, low, mid-1);
   }


   public static void main(String[] args) {
      BinarySearchRecursive bin =
         new BinarySearchRecursive();
      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,97};  // 20-28
      for (int i = 0; i < a.length; i++)
         System.out.print(bin.binarySearch(a,
            a[i]) + " ");
      System.out.println();
      System.out.print(bin.binarySearch(a,1) +" ");
      System.out.print(bin.binarySearch(a,26)+" ");
      System.out.print(bin.binarySearch(a,85)+" ");
      System.out.print(bin.binarySearch(a,99)+" ");
      System.out.println();
   }
}
Common Output
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

Next, I have translated the two searches into C. For a real implementation one would want the binary search in a separate file, with a header file, etc. Also of course we wouldn't want the code hardwired for a specific file of length 29. Otherwise these are similar to the Java programs and the same comments apply.

C Binary Search, With and Without Recursion
// binarysearch.c: simple implementation
#include <stdio.h>
#define LEN 29





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

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,97};  // 20-28
   int i;
   for (i = 0; i < 29; i++)
      printf("%i ", binarysearch(LEN, a, a[i]));
   printf("\n");
   printf("%i ", binarysearch(LEN, a, 1));
   printf("%i ", binarysearch(LEN, a, 17));
   printf("%i ", binarysearch(LEN, a, 42));
   printf("%i ", binarysearch(LEN, a, 99));
   printf("\n");
}

// binsearchrec.c: simple implementation
#include <stdio.h>
#define LEN 29

int binsearchrec(int len, int a[], int x) { 
   return binsearchrec0(len, a, x, 0, LEN - 1);
}

int binsearchrec0(int len, int a[], int x,
         int low, int high) {
   int mid;
   if (low > high) return -1; 
   mid = (low + high)/2;
   if (a[mid] == x) return mid;
   else if (a[mid] < x)
      return binsearchrec0(LEN, a, x, mid+1,high);
   else // last possibility: a[mid] > x
      return binsearchrec0(LEN, a, x, low, mid-1);
}

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,97};  // 20-28
   int i;
   for (i = 0; i < 29; i++)
      printf("%i ", binsearchrec(LEN, a, a[i]));
   printf("\n");
   printf("%i ", binsearchrec(LEN, a, 1));
   printf("%i ", binsearchrec(LEN, a, 17));
   printf("%i ", binsearchrec(LEN, a, 42));
   printf("%i ", binsearchrec(LEN, a, 99));
   printf("\n");
}
Common Output
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

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