Algorithms for Coding Interviews in C++/

...

/

Solution: Search in Sorted Matrix

Solution: Search in Sorted Matrix

This review lesson gives a detailed analysis of the solutions to search a target in a sorted matrix.

We'll cover the following...

Solution #1: Brute Force

C++
int search(vector<vector<int>> matrix, int numberOfRows, int numberOfColumns, int target) {
  for (int i = 0; i < numberOfRows; i++) {
    for (int j = 0; j < numberOfColumns; j++) {
      if (matrix[i][j] == target)
        return 1;
    }
  }
  return 0;
}
int main() {
  vector<vector<int>> matrix = { {10, 11, 12, 13}, {14, 15, 16, 17}, {27, 29, 30, 31}, {32, 33, 39, 80} };
  
  // Example 1
 if (search(matrix, 4, 4, 80))
    cout << "80 is Found" << endl;
  else
    cout << "80 is Not Found" << endl;
  
  // Example 2
   if (search(matrix, 4, 4, 37))
    cout << "37 is Found" << endl;
  else
    cout << "37 is Not Found" << endl;
  return 0;
}

This is a simple linear searching of the 2-D Matrix. We use two for loops to iterate over the entire matrix.

Time complexity

Since we use two nested for loops, the time complexity is O(n∗m)O(n*m) ...