Searching in a sorted array of strings with empty strings

Problem

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “"] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “"] will return -1

Solution
The worst we can do is O(n) where we just do a linear search.

I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.

public static int findLocation(String\[\] array, int i, int j, String str) {  
    int mid;  
    while (i <= j) {  
        mid = (i + j) / 2;  
        if (array\[mid\].equals("")) {  
            int leftIndex = findLocation(array, i, mid - 1, str);  
            if (leftIndex == -1)  
                return findLocation(array, mid + 1, j, str);  
            else  
                return leftIndex;  
        } else {  
            if (str.compareTo(array\[mid\]) == 0)  
                return mid;  
            if (str.compareTo(array\[mid\]) < 0)  
                j = mid - 1;  
            if (str.compareTo(array\[mid\]) > 0)  
                i = mid + 1;  
        }  
    }  
    return -1;  
}

**References **
http://tianrunhe.wordpress.com/2012/03/31/searching-in-a-sorted-array-of-strings-with-empty-strings/

See also