**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/

## 0 comments:

## Post a Comment