The Fake Geek's blog: Search string in sparse array
Search string in sparse array
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
This follows the ordinary binary search. However, notice that when the mid is an empty string, you should either proceed right or left to find the first nonempty string.
Besides, use start <= last and start = mid + 1
Read full article from The Fake Geek's blog: Search string in sparse array
No comments:
Post a Comment