Sparse Search

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

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

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

Careful consideration should be given to the situation when someone searches for t he empty string. Should we find the location (which is an O( n) operation)? Or should we handle this as an error?

There's no correct answer here. This is an issue you should raise with your interviewer. Simply asking this question will demonstrate that you are a careful coder.

Read full article from Sparse Search - 小土刀的面试刷题笔记