What is a Binary Search?

The class below implements and tests a binary search algorithm. A binary search works by taking a sorted array and repeatedly taking the middle element of the array. If the middle element is the target, the index is returned. If the target is lower than the middle element, it proceeds to search the midpoint of the elements left of the last midpoint. If the target is higher than the middle element, it proceeds to search the midpoint of the elements higher than the last midpoint.

How Does it Perform?

This divides the result set in half on each search attempt which makes it log(n) performance.  To put this in perspective, this means you can find the target element in a one-billion record array within 30 iterations (30 being the worst case scenario).

public class BinarySearch {

     //Perform binary search if the provided array actually
     //contains values.
     public static int binarySearch(int[] a, int target) {
         if (a == null || a.length == 0) return -1;
         return binarySearch(a, target, 0, a.length - 1);
     }

     //Recursive binary search algorithm taking in the array,
     //target value, and the start and end indices (inclusive
     //end is the last element, not one past the last element.
     private static int binarySearch(int[] a, int target,
             int start, int end) {

         //If we're at the last element, check it against the target.
         //Return index on match and -1 on failure.
         if (start == end) return a[start] == target ? start : -1;

         //Get the midpoint index and the value present in it.
         int midIndex = (start + end) / 2;
         int midValue = a[midIndex];

         //If the midpoint is the target, return its index.
         if (midValue == target) return midIndex;

         //If the midpoint wasn't the target, recurse to look lower
         //if the value was less than the middle value or recurse to
         //search higher if the value was greater than the midpoint.
         if (target < midValue)
             return binarySearch(a, target, start, midIndex - 1);

         return binarySearch(a, target, midIndex + 1, end);
     }

     //Test the algorithm and throw an exception on failure.  This
     //should be a JUnit test, but it is being left as a main in
     //this class to make the example standalone.
     public static void main(String[] args) throws Exception{

         //Make a sample array - must be sorted for search to work.
         int[] a = { 1, 4, 7, 9, 13, 15, 18, 21, 37, 56, 72 };

         final String error = "Unexpected result, algorithm failed.";

         //Run test assertions.
         if(!(binarySearch(a, 9) == 3)) throw new Exception(error);
         if(!(binarySearch(a, 4) == 1)) throw new Exception(error);
         if(!(binarySearch(a, 7) == 2)) throw new Exception(error);
         if(!(binarySearch(a, 1) == 0)) throw new Exception(error);
         if(!(binarySearch(a, 13) == 4)) throw new Exception(error);
         if(!(binarySearch(a, 15) == 5)) throw new Exception(error);
         if(!(binarySearch(a, 18) == 6)) throw new Exception(error);
         if(!(binarySearch(a, 21) == 7)) throw new Exception(error);
         if(!(binarySearch(a, 37) == 8)) throw new Exception(error);
         if(!(binarySearch(a, 56) == 9)) throw new Exception(error);
         if(!(binarySearch(a, 72) == 10)) throw new Exception(error);

         //Test some cases that should return -1 (not found).
         if(!(binarySearch(a, 27) == -1)) throw new Exception(error);
         if(!(binarySearch(a, 10) == -1)) throw new Exception(error);

         //Print the success log.
         System.out.println("All results were as expected.");
     }
 }