leetcode 74. Search a 2D Matrix

题目描述

要求时间复杂度必须是log(m*n)。那么对每一行分别执行二分查找就不符合要求，这种做法的时间复杂度是m*log(n)。

方法一，对每一行分别执行二分查找：

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();for(int i = 0;i < m;i++){if(binary_search(matrix[i],0,n-1,target))return true;}return false;}bool binary_search(vector<int> row,int left,int right,int target){int mid = 0;while(left <= right){mid = left + ((right-left)>1);if(row[mid] == target)return true;else if(row[mid] > target){right = mid-1;}else{left = mid+1;}}return false;}
};

 方法二，对整个矩阵执行二分查找，关键是要将整体的序号映射到行和列的下标：

时间复杂度log(m*n)，符合要求。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();int left = 0;int right = m*n-1;int mid = 0;int row = 0;int column = 0;while(left<=right){mid = left+((right-left)>>1);row = mid/n;column = mid%n;if(matrix[row][column] == target)return true;else if(matrix[row][column] > target){right = mid -1;}else{left = mid + 1;}}return false;}
};