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/