Concise C++ solution - Binary Search


  • 3
    N

    I label the grid from 0 - n * m -1. The numbers are ascending. So Binary Search works in this case.

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

Log in to reply
 

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