Sparse Search

10.5 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

• Worst case order O(n), Avg. O(logN), O(N) space

• Algorithm: Just ignore the empty strings. If you find an empty string, then preform a radial search outwards from that location until you find a non-empty string. This works because all be need is the closest thing to compare the target string with the middle. Technically, either the right or left string from the space could work, because either one will notify us whether we need to search right or left. We just chose the faster alternative.

int binary_search(vector<string> &strs, int low, int high, string target) {
    if (high < low) return -1;

    int middle = low + ((high - low) / 2);

    if (strs.at(middle).empty()) {
        int left = middle - 1;
        int right = middle + 1;

        while (left > low && right < high) {
            if (strs.at(left).empty())
                left--;
            else {
                middle = left;
                break;
            }
            if (strs.at(right).empty())
                right++;
            else {
                middle = right;
                break;
            }
        }
    }

    if (strs.at(middle) == target) return middle;
    // search right
    else if (strs.at(middle) < target) {
        binary_search(strs, middle + 1, high, target);
    }
    else {
        binary_search(strs, low, middle - 1, target);
    }
}

int sparse_search(vector<string> &strs, string str) {
    if (strs.empty() || str == "") return -1;
    return binary_search(strs, 0, strs.size() - 1, str);
}


int main() {
    vector<string> strings = { "at", "", "", "", "ball", "", "", "car", "", "", "dad", "", "" };
    cout << sparse_search(strings, "ball") << endl;
}