BinarySearch.java

/* 
 * Binary search is an efficient, O(log n) search on a sorted array
 * which works by eliminating half of the search area for each comparison 
 * between the current middle element and the search target.
 */
public class BinarySearch {
    
    /**
     * Performs a binary search
     *
     * @param arr a sorted array of Comparable objects
     * @param target the search value
     * @return the index of the object if found in the array, else -1
     */
    public static int search(Comparable[] arr, Comparable target) {
        return arr == null || arr.length > 0 ? 
            search(arr, target, 0, arr.length - 1) : -1;  
    }
    
    private static int search(Comparable[] arr, Comparable target, int lo, int hi) {

        // Search indexes crossed; item not in array
        if (lo > hi) { return -1; }

        // Find the middle element
        int mid = (hi - lo) / 2 + lo;
        
        // Compare the search target with the current middle element in the array
        int comparison = target.compareTo(arr[mid]);
        
        if (comparison == 0) { // target found, return its index
            return mid;
        }
        else if (comparison < 0) { // search the lower half of the array
            return search(arr, target, lo, mid - 1);
        }
        else { // comparison > 0, search the upper half of the array
            return search(arr, target, mid + 1, hi);
        }
    }
    
    // Test
    public static void main(String[] args) {
        System.out.println(search(
            new String[] { "a", "b", "c", "f", "y" }, "c"));
        System.out.println(search(
            new String[] { "a", "b", "c", "f", "y" }, "y"));
        System.out.println(search(
            new String[] { "b", "b", "c", "f", "y" }, "a"));
        System.out.println(search(
            new String[] { "a", "b", "b", "f", "y" }, "b"));
        System.out.println(search(
            new String[] { "a", "b", "c", "f", "y" }, "z"));
        System.out.println(search(
            new String[] { "a", "b", "c", "f" }, "a"));
        System.out.println(search(new String[] { }, "x"));
        System.out.println(search(new String[] { "x" }, "z"));
        System.out.println(search(new String[] { "x" }, "a"));
        System.out.println(search(new String[] { "x" }, "x"));
        System.out.println(search(new Integer[] { 1, 3 }, 3)); 
        System.out.println(search(new String[] { "t", "x" }, "t")); 

        // Ensure all indexes can be found in array
        Integer[] arr = { 1,4,8,9,5345,24543,342455,4328382 };
        for (int i = 0; i < arr.length; i++) {
            System.out.print(search(arr, arr[i]) + " ");
        }
        
        System.out.println();
        
        // Ensure all indexes not in array won't be found
        Integer[] arr2 = { 0,2,3,11,5145,22543,3421155,4328384 };
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(search(arr, arr2[i]) + " ");
        }
    }
}