C++ 12ms Solution using Binary Search [O(log(m) + log(n))]


  • 8
    J
    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int m = matrix.size(), n = matrix[0].size(), x, y;
            int lo = 0, hi = m*n-1, mid;
            if (hi == 0) return (matrix[0][0] == target);
            while (lo <= hi)
            {
                mid = lo + (hi-lo)/2;
                x = mid / n; y = mid % n;
                if (matrix[x][y] == target)
                    return true;
                else if (matrix[x][y] > target)
                    hi = mid-1;
                else
                    lo = mid+1;
            }
            return false;
        }
    };

  • 0
    L

    My solution also use Binary Search, where the boundary values are also checked within one loop.

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int start = 0;
            int end = matrix.size();
            if(end == 0) return false;
            int len = matrix[0].size();
            end = end * len - 1;
            
    
            int mid;
            while(start <= end){
                mid = (start + end)/2;
                
                int i = start / len;
                int j = start % len;
                if(matrix[i][j] > target) return false;
                if(matrix[i][j] == target) return true;
                
                i = end / len;
                j = end % len;
                if(matrix[i][j] < target) return false;
                if(matrix[i][j] == target) return true;
                
                i = mid / len;
                j = mid % len;
                if(matrix[i][j] == target) return true;
                if(matrix[i][j] < target) {
                    start = mid + 1;
                    end --;
                } else {
                    start++;
                    end = mid - 1;
                }
            }
            
            return false;
    
        }
    };
    

Log in to reply
 

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