Leetcode Search a 2 D Matrix検索2 Dテーブル

Search a 2D Matrix
 
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target =  3 , return  true .
この問題の解法は多いが、ネット上でも分析されている.
例えばLeetCodeフォーラムでは分析が非常に細かいが、彼が推薦したのはO(n+m)の時間効率のようで、今回も例外で、彼の分析も例もよくない.
この問題の最適時間効率はO(lgm+lgn)であるべきであるからである.m,nは行と列数を代表して、しかもそんなに複雑ではありませんが、二分法の運用を試験して、この問題を柔軟に運用することができるのは難しいことではありません.
ここでは二分法を使って、まず二分を並べて、それから二分を行います.複雑に見えますが、実は簡単なプログラムです.Leetcodeのそんなに長編大論の分析を見る必要はありません.
次は私のプログラムで、長いように見えますが、実は構造がはっきりしていて、よく理解しているプログラムです.

	const static int FOUND = -2;
	const static int NOT_FOUND = -1;

	bool searchMatrix(vector<vector<int> > &matrix, int target) 
	{
		int found_mark = searchRow(matrix, 0, matrix.size()-1, target);
		if (found_mark == NOT_FOUND) return false;
		if (found_mark == FOUND) return true;

		found_mark = searchCol(matrix, found_mark, 0, matrix[0].size()-1, target);

		if (found_mark == NOT_FOUND) return false;
		return true;
	}

	int searchRow(vector<vector<int> > &m, int low, int up, int tar)
	{
		//up = -1       NOT_FOUND,   NOT_FOUND=-1
		if (low > up) return up;

		int mid = low + ((up - low)>>1);
		if (tar < m[mid][0])
		{
			return searchRow(m, low, mid-1, tar);
		}
		else if (m[mid][0] < tar)
		{
			return searchRow(m, mid+1, up, tar);
		}
		else return FOUND;
	}

	int searchCol(vector<vector<int> > &m, int row, int left, int right, int tar)
	{
		if (left > right) return NOT_FOUND;

		int mid = left + ((right - left)>>1);
		if (tar < m[row][mid])
		{
			return searchCol(m, row, left, mid-1, tar);
		}
		else if(m[row][mid] < tar)
		{
			return searchCol(m, row, mid+1, right, tar);
		}
		else return FOUND;
	}

次はLeetcodeのプログラムも見てみましょう.簡単ですが、面接官に必要な答えかもしれません.では、O(lgn+lgm)がO(n+m)より1ランクアップした時間の複雑さを疑ってみましょう.もちろん二分法です.

//     ，            ，   O(n+m)
	bool searchMatrix2(vector<vector<int> > &matrix, int target) {
		int m(matrix.size()-1), n(matrix[0].size()), k(0);
		while(m>=0 && k<n){
			if(matrix[m][k]==target) return true;
			else if(matrix[m][k]>target) --m;
			else ++k;
		}
		return false;
	}

//2004-2-11 update
	bool searchMatrix(vector<vector<int> > &matrix, int target) 
	{
		int row = colSearch(matrix, 0, matrix.size()-1, target);
		if (row == -1) return false;
		return rowSearch(matrix, row, 0, matrix[row].size()-1, target);
	}
	int colSearch(vector<vector<int> > &m, int c1, int c2, int tar)
	{
		if (c1 > c2) return -1;
		int mid = c1 + ((c2-c1)>>1);
		if (m[mid][0]<=tar && tar<=m[mid].back()) return mid;
		if (m[mid][0] < tar) return colSearch(m, mid+1, c2, tar);
		if (tar < m[mid][0]) return colSearch(m, c1, mid-1, tar);
		return -1;
	}
	bool rowSearch(vector<vector<int> > &m, int row, int r1, int r2, int tar)
	{
		if (r1 > r2) return false;
		int mid = r1 + ((r2-r1)>>1);
		if (m[row][mid] < tar) return rowSearch(m, row, mid+1, r2, tar);
		if (tar < m[row][mid]) return rowSearch(m, row, r1, mid-1, tar);
		return true;
	}