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