## Searching in a sorted array of strings with empty strings

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 $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.

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

Worst case time complexity is still $O(n)$ 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.

__ATA.cmd.push(function() {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});