Find String in Array Interspersed with Empty Strings

Book: Cracking the Coding Interview
Question: 11.5 (page 121)

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
EXAMPLE:
Input: find "ball" in {"at", "", "", "", "ball", "", "car", "", "", "dad", "", ""}
Output: 4

Solution: Average case: O(log(n)), Worst case: O(n/2) => O(n)