Sparse Search
problem
Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.
how to solve
If it were not for the empty strings, we could simply use binary search. With empty strings interspersed, we can implement a simple modification of binary search. We just find closest non-empty string if mid is empty.