Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Sparse Search

Understand how to solve the sparse search problem using two approaches: a brute force method that scans the array linearly and a modified binary search that skips empty strings. Learn to apply these techniques effectively to handle sparsely filled sorted arrays and analyze their time complexities.

We'll cover the following...

Solution #1: Brute Force

C++
int searchForString(string array[], int size, string target) {
  for (int i = 0; i < size; i++) {
    if (array[i] == target) {
      return i;
    }
  }
  return -1;
}
int main() {
  int size = 12;
  string array[size] = {"", "educative", "", "", 
                        "",  "hello", "", "learning", 
                        "world", "", "", ""};
  
  string targetArray[2] = {"educative", "learning"};
  
  for(int i = 0; i < 2; i++) {
    cout << targetArray[i] << ": " << searchForString(array, size, targetArray[i]) << endl;
  }
  return 0;
}

In this solution we traverse the entire array of strings and stop only if we find the target string or reach the end of array.

Time Complexity

The time complexity is the time it takes to traverse the entire array, i.e. O ...