Find the location of the given string from a sorted array of string which is interspersed 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
Input: find “ball” in {“at”, “”, “”, "ball”, "”, "”, "car”,“”, "”, "dad”, ”“, ”“}
Output:4
Solution
There are some points in problem sentence. One is a sorted array, and other one is that there are empty strings.
Sorted Array
When we search a object from sorted array, we can use binary search tree. So this problem can be solved by using binary search tree basically.
Array is interspersed with empty strings
But, this array is interspersed with empty string. So if the middle value is empty string, we have to check the left and right side until the string will be exist string.