Sparse Search

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string

EXAMPLE

Input: ball, {at, ,, , ball,, , car,, , dad,, ""}
Output: 4

Solution

In case mid is an empty string. We simply move mid to the closest non-empty string

Code

``````int search(String[] strings, String str, int first, int last){
if (first > last) return -1;
int mid = (last + first) / 2;

// If mid is empty, find closest non-empty string
if (strings[mid].isEmpty()){
int left = mid - 1;
int right = mid + 1;
while (true){
if (left < first && right > last){
return -1;
}
else if (right <= last && !strings[right].isEmpty()){
mid = right;
break;
}
else if (left >= first && !strings[left].isEmpty()){
mid = left;
break;
}
right++;
left--;
}
}

if (str.equals(strings[mid])){ // Found it!
return mid;
}
else if (strings[mid].compareTo(str) < 0){ // Search right
return search(strings, str, mid + 1, last);
}
else {
return search(strings, str, first, mid - 1);
}
}
``````