search-a-2d-matrix

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

题解

先二分法找行，再二分法找列。

最后提交的版本：

bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int row = matrix.size();
	if (!row)return false;
	int col = matrix[0].size();
	if (!col)return false;

	int up = 0, down = row-1, mid = 0;
	while (up <= down)
	{
		mid = (up + down) / 2;
		if (matrix[mid][0] == target)return true;
		else if (matrix[mid][0] > target)
			down = mid - 1;
		else if (matrix[mid][col - 1] < target)
		{
			up = mid + 1;
		}
		else
			break;
	}
	int left = 0, right = col-1, center;
	while (left <= right)
	{
		center = (left + right) / 2;
		if (matrix[mid][center] == target)return true;
		else if (matrix[mid][center] < target)left = center+1;
		else right = center-1;
	}
	return false;
}

下面是修改之前找行数的while循环。修改之后的明显时间上快了许多。

while (up <= down)
	{
		mid = (up + down) / 2;
		if (matrix[mid][0] > target)
			down = mid-1;
		else if (matrix[mid][0] < target)
		{
			if (mid<row - 1 && matrix[mid + 1][0]>target)
				break;
			up = mid+1;
		}
		else
			return true;
	}