## Saturday, March 29, 2014

### Searching in a sorted array of strings 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: find “ball” in ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""] will return 4
Example: find “ballcar” in ["at", "", "", "", "", "ball", "car", "", "", "dad", "", ""] will return -1

Solution
The worst we can do is O(n) where we just do a linear search.

I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.
```public static int findLocation(String[] array, int i, int j, String str) {
int mid;
while (i <= j) {
mid = (i + j) / 2;
if (array[mid].equals("")) {
int leftIndex = findLocation(array, i, mid - 1, str);
if (leftIndex == -1)
return findLocation(array, mid + 1, j, str);
else
return leftIndex;
} else {
if (str.compareTo(array[mid]) == 0)
return mid;
if (str.compareTo(array[mid]) < 0)
j = mid - 1;
if (str.compareTo(array[mid]) > 0)
i = mid + 1;
}
}
return -1;
}
```

References
http://tianrunhe.wordpress.com/2012/03/31/searching-in-a-sorted-array-of-strings-with-empty-strings/