C++, 12 lines, 9ms, O(logm + logn), binary search row first


  • 0
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.size() == 0 || matrix[0].size() == 0) return false;
            int lo(0), hi(matrix.size()-1);
            int mid = (lo + hi) / 2;
            while(lo < hi){
                if(matrix[mid][0] < target) lo = mid + 1;
                else if(matrix[mid][0] > target) hi = mid - 1;
                else return true;
                mid = (lo + hi) / 2;
            }
            if(matrix[lo][0] > target && lo != 0) lo--;
            int i = lower_bound(matrix[lo].begin(), matrix[lo].end(), target) - matrix[lo].begin();
            return matrix[lo][i] == target;
        }
    

Log in to reply
 

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