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

**My initial thoughts:**

The worst we can do is 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 search but in average, it’s better off.

**My initial codes:**

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;
}

**Solution:**

public static int search(String[] strings, String str, int first, int last) {
while (first <= last) {
// Ensure there is something at the end
while (first <= last && strings[last] == "") {
--last;
}
if (last < first) {
return -1; // this block was empty, so fail
}
int mid = (last + first) >> 1;
while (strings[mid] == "") {
++mid; // will always find one
}
int r = strings[mid].compareTo(str);
if (r == 0)
return mid;
if (r < 0) {
first = mid + 1;
} else {
last = mid - 1;
}
}
return -1;
}
public static int search(String[] strings, String str) {
if (strings == null || str == null)
return -1;
if (str == "") {
for (int i = 0; i < strings.length; i++) {
if (strings[i] == "")
return i;
}
return -1;
}
return search(strings, str, 0, strings.length - 1);
}

Comments:

- Worst case time complexity is still since in the worst case, you need to remove all the “”s.
- Covers the cases where the target we are looking for is indeed, empty string. Also some error conditions have been handled.

### Like this:

Like Loading...

*Related*