# 10.5. Sparse search

> Given a sorted array of strings that is interspersed with empty strings, find the location of a given string

Example:

* array = ['at', '', '', '', 'ball', '', '', 'car', '', '', 'dad, '', '']
* word = ball
* Output: 4

We don't know how many empty strings there are between words. We could sort it to get rid of empty strings, and search in the sorted array. This would take O(nlog(n)) I believe for sorting + O(log(n)) for searching = O(nlog(n)). We would implement the binary search so that if the middle point is empty, calculate middle point between left and middle again until we find a word.

The solution mentions doing binary search and if the middle point is empty, move mid to the closest non-empty string. The worst case scenario is O(n), since you can have an array full of empty strings except one.

Consider what happens if the word to be searched is an empty string, should the algorithm return an error? Discuss with the interviewer
