One binary search to find the row of target value and another to find the target in that row!!!! O(log(row)+log(col))


  • 1
    R
     bool searchMatrix(vector<vector<int>>& matrix, int target) {
                int r=matrix.size() , c=matrix[0].size(),mid;
        // condition to check target is in matrix range  
                if(target < matrix[0][0] || target > matrix[r-1][c-1]) return false;
        //first binary search to find the row number in which the target is present      
                int s=0 , e=r-1; 
                while(s <= e){
                    mid =s+ (e-s)/2;
                    if(matrix[mid][c-1] < target) s = mid+1;
                    else e = mid-1;
                }
        // after the above binary search the s will store the row number of the target ,
        // note that is after this binary search s=r (if target is greater than largest element matrix[r-1][c-1]
        // and s=0 (s is in first row or less than the least element matrix[0][0]).
        // since i have considered both these cases earlier using two if conditions , otherwise i can use 
        // this if condition here   **  if(s == r) return false; **
                int left = 0, right = c-1;
                while(left <= right){
                    mid = left + (right-left)/2;
                    if(matrix[s][mid] == target) return true;
                    else if(matrix[s][mid] > target) right = mid-1;
                    else left = mid+1;
                }
        // target is not present in matrix
                return false;  
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.