search-a-2d-matrix

gistfile1.cpp

https://oj.leetcode.com/problems/search-a-2d-matrix/

/*
I think the the most important hint is the fact that this matrix is already sorted.
just think of the binary search.
I could know the length of each row, thus start from the first element of the middle row(2/n), compare then move to 4/n ... 

test case1
long column: [1,2,3,4,5,6,7,8,9,10,11,12...]

test case2
long row: [1]
          [2]
          [3]
          ...
          
Psuedo-code          
if target>matrix[middle][colMiddle] 
    if target > matrix[middle][colLength] {
        
    else if <  
        colMiddle = (colMiddle+colLength)/2
    else 
        return true;
else if(target<) ...


Failure 1: [[1]], 0 TLE -> while loop condition change from (rowLeft <= rowRight || colLeft <= colRight) to (rowLeft <= rowRight && colLeft <= colRight)

*/

class Solution {
public:
    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int rowLeft = 0;
        int colLeft = 0;
        int rowRight = matrix.size()-1;
        
        if(rowRight < 0) {
            return false;
        }
        
        int colRight = matrix[0].size()-1;
        
        while(rowLeft <= rowRight && colLeft <= colRight) {
            int rowMiddle = (rowLeft+rowRight)/2;
            int colMiddle = (colLeft+colRight)/2;
            
            if(matrix[rowMiddle][colMiddle] == target) {
                
                return true;
            } else if(matrix[rowMiddle][colMiddle] > target) {
                if(matrix[rowMiddle][colLeft] == target) {
                    
                    return true;    
                } else if(matrix[rowMiddle][colLeft] < target) {
                    colRight = colMiddle-1;
                } else if(matrix[rowMiddle][colLeft] > target) {
                    rowRight = rowMiddle-1;
                }
            } else if(matrix[rowMiddle][colMiddle] < target) {
                if(matrix[rowMiddle][colRight] == target) {
                    
                    return true;    
                } else if(matrix[rowMiddle][colRight] < target) {
                    rowLeft = rowMiddle+1;
                } else if(matrix[rowMiddle][colRight] > target) {
                    colLeft = colMiddle+1;
                }
            }
        }
        
        return false;
    }
};