Recursive Binary Search

Recall that the binary search in general is where we split the ordered array in two, and ask if the item being looked for is greater or lesser than the mid. If greater, then we can disregard everything less than the mid, and if lesser, then we can disregard everything higher than the mid. In this way, we can narrow down where the value is in a very efficient, logarithmic in fact, way.

It's all about the order in which the parameters are sent in the recursive calls. So look at lines 16 and 18, in particular.
- Line 16 would be executed in each case where the value being looked for is greater than the current mid. So high remains the same, but the new low is mid + 1.
- And line 18 would be executed when the value being looked for is less than the current mid. So what get passed as high and low are the same low, and mid - 1.

The other modest thing to note is that this is for type Comparable - so any type, like String, which has inherited the class Comparable.

/Users/adelaide/Public/Netbeans - All JSR Projects/JavaApplication1/src/javaapplication1/ToShowBothBinarySearches.java

  1 package javaapplication1;
  2 
  3 
  4 public class ToShowBothBinarySearches {
  5 
  6     public static int iterativeBinarySearch(int arr[], int key) {
  7         int low = 0;
  8         int high = arr.length - 1;
  9         while (low <= high) {
 10             int mid = (low + high) / 2;
 11             if (arr[mid] == key) {
 12                 return mid;
 13             } 
 14             else if (arr[mid] < key) {
 15                 low = mid + 1;
 16             } 
 17             else {
 18                 high = mid - 1;
 19             }
 20         }
 21         return -1;
 22     }
 23 
 24     private static int recursiveBinarySearch(int[] arr, int key, int low, int high) {
 25         //See way below for a nicer recursiveBinarySearch, which doen't require you the user of the method
 26         //to send a high and a low value, which is not necessary if.... well, look below for what is needed.
 27         if (low > high) {
 28             return -1;
 29         }
 30 
 31         int mid = (low + high) / 2;
 32 
 33         if (arr[mid] < key) {
 34             return recursiveBinarySearch(arr, key, mid + 1, high);
 35         } 
 36         else if (arr[mid] > key) {
 37             return recursiveBinarySearch(arr, key, low, mid - 1);
 38         } 
 39         else {
 40             return mid;
 41         }
 42     }
 43 
 44     public static void main(String[] args) {
 45 
 46         //          [0] [1]  [2] [3] [4]  [5]    [6]    [7]
 47         int[] arr = {2, 24, 35, 68, 79, 102, 203, 4567};
 48 
 49         for (int i = 0; i < arr.length; i++) {
 50             System.out.println(arr[i]);
 51         }
 52         int answer = iterativeBinarySearch(arr, 35);
 53         System.out.println("The number 4644 was found via the "
 54                 + "iterative binary search at the index: " + answer);
 55 
 56         int answerRecursiveWay = recursiveBinarySearch(arr, 35, 0, arr.length - 1);
 57         System.out.println("The number 4644 was found via the "
 58                 + "recursive binary search at the index: " + answerRecursiveWay);
 59         
 60         int answerRecursiveWay2 = nicerRecursiveBinarySearch(arr, 35);
 61         System.out.println("The number 4644 was found via the "
 62                 + "nice recursive binary search at the index: " + answerRecursiveWay2);
 63 
 64     }
 65     
 66     
 67     
 68     
 69     
 70     private static int nicerRecursiveBinarySearch(int[] arr, int key) {
 71         //So this is called only once, from the person using this class. But all calls from now on
 72         //have to be to the HELPER recursive binary search, because the low and high will not
 73         //be 0 and length - 1 from this call onward.
 74         int low = 0; 
 75         int high = arr.length - 1;
 76         
 77         if (low > high) {
 78             return -1;
 79         }
 80 
 81         int mid = (low + high) / 2;
 82 
 83         if (arr[mid] < key) {
 84             return nicerRecursiveBinarySearchHELPER(arr, key, mid + 1, high);
 85         } 
 86         else if (arr[mid] > key) {
 87             return nicerRecursiveBinarySearchHELPER(arr, key, low, mid - 1);
 88         } 
 89         else {
 90             return mid;
 91         }
 92     }
 93     
 94     private static int nicerRecursiveBinarySearchHELPER(int[] arr, int key, int low, int high) {
 95         
 96         if (low > high) {
 97             return -1;
 98         }
 99 
100         int mid = (low + high) / 2;
101 
102         if (arr[mid] < key) {
103             return nicerRecursiveBinarySearchHELPER(arr, key, mid + 1, high);
104         } 
105         else if (arr[mid] > key) {
106             return nicerRecursiveBinarySearchHELPER(arr, key, low, mid - 1);
107         } 
108         else {
109             return mid;
110         }
111     } 
115     
116 }
117