Posted on

Search Sorted Matrix Solution in C++

The idea here is to implement binary search after discovering the correct row.


#include <bits/stdc++.h>
using namespace std;



class Solution {
  public:
  
  
    // Function to search a given number in row-column sorted matrix.
    bool searchMatrix(vector<vector<int>> &mat, int x) {
        // code here
        vector<int>*row = nullptr;
        int rows = mat.size();
        int cols = mat[0].size();
        
        for( int i = 0; i < rows; i++ ){
            if( mat[i][0] <= x && mat[i][cols-1] >= x ){
                row = &(mat[i]);
                break;
            }
        }
        
        if( row == nullptr ) return false;
        
        auto binarySearch = [row, x]( int low, int high ) -> bool{
            
            while( low <= high ){
                int mid = low + (high-low)/2;
            
                if( (*row)[mid] == x ){
                    return true;
                }else if((*row)[mid] < x ){
                    low =  mid + 1;
                } else {
                    high = mid - 1;
                }
                
            }
            
            return false;
            
        };   
        
        return binarySearch(0, cols -1 );
    }
};