[LeetCode]Search a 2D Matrix

假设输入矩阵为m * n，那么我们就可以就可以将这个2D matrix看做一个长度为m * n的1D array，我们再对其进行二分搜索即可，时间复杂度为O(log(m * n))，代码如下：

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

view raw Search a 2D Matrix_1.cpp hosted with ❤ by GitHub

当然我们也可以先进行列的搜索，再进行行的搜索。我们先搜索第一列，如果可以找到target number直接return。否则找到小于target number的最大数，然后从那里开始对行进行搜索，因为如果target number如果存在，其一定在那一行。时间复杂度O(log(m) + log(n))，代码如下：

	class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int m = matrix.size(), n = m ? matrix[0].size() : 0, lo = 0, hi = m - 1;
	if (!m || !n)return false;
	//find column start with largest value lower than target
	while (lo <= hi)
	{
	int mid = lo + (hi - lo) / 2;
	int curr = matrix[mid][0];
	if (curr < target)lo = mid + 1;
	else if (curr > target)hi = mid - 1;
	else return true;
	}
	if (hi < 0)return false;
	int i = hi;
	lo = 0, hi = n - 1;
	//find in row
	while (lo <= hi)
	{
	int mid = lo + (hi - lo) / 2;
	int curr = matrix[i][mid];
	if (curr < target)lo = mid + 1;
	else if (curr > target)hi = mid - 1;
	else return true;
	}
	return false;
	}
	};

view raw Search a 2D Matrix_2.cpp hosted with ❤ by GitHub