Matsushita's Blog

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.

Source Code