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

Solution: Search in Sorted Matrix

Understand different approaches to search in a sorted matrix. This lesson covers brute force linear search, optimized moving direction search, and binary search, explaining their time complexities and when to apply each method.

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) ...