My concise 8 lines c++ code with O(logm + logn) complexity


  • 0
    W
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    	int m = matrix.size(), n = matrix[0].size();
    	int l = 0, r = m*n-1;
    	while (l<=r) {
    		int mid = l+(r-l)/2, mid_x = mid/n, mid_y = mid-n*mid_x;
    		if (matrix[mid_x][mid_y]==target) return true;
    		if (matrix[mid_x][mid_y]<target) l = mid+1;
    		else r = mid-1;
    	}
    	return false;
    }

Log in to reply
 

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