二维数组中查找（暴力遍历、二叉树搜索）

vector容器构建二维数组

	std::vector row1 = { 1,4,7,11,15 };
	std::vector row2 = { 2,5,8,12,19 };
	std::vector row3 = { 3,6,9,16,22 };
	std::vector row4 = { 10,13,14,17,24 };
	std::vector row5 = { 18,21,23,26,30 };
	std::vector> matrix{ row1,row2,row3,row4,row5 };

获取二维数组行列

int row = matrix.size();      //行
int col = matrix[0].size();   //列

增加操作

matrix[1].push_back(23);   //插入列元素23
matrix.push_back(row1);     //插入一行

删除操作

matrix.erase(matrix.begin()+1);//删除第2行
matrix[1].erase(a[1].begin() + 2);//删除第二行第三列元素

遍历

int row = matrix.size();
int col = matrix[0].size();
for (int i = 0; i < row; i++) {
	for (int j = 0; j < col; j++) {
		std::cout << matrix[i][j]<<'t';
			
	}
	std::cout << std::endl;
}

问题：

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

方法一：暴力遍历查找

class Solution {
public:
	bool findNumberIn2DArray(std::vector>& matrix, int target) {
		int row = matrix.size();
		int col = matrix[0].size();
		for (int i = 0; i < row ; i++) {
			for (int j = 0; j < col ; j++) {
				//std::cout << matrix[i][j]<<'t';
				if (matrix[i][j] == target) return true;
			}
			//std::cout << std::endl;
		}
		return false;
	}	
};

int main() {
	std::vector row1 = { 1,4,7,11,15 };
	std::vector row2 = { 2,5,8,12,19 };
	std::vector row3 = { 3,6,9,16,22 };
	std::vector row4 = { 10,13,14,17,24 };
	std::vector row5 = { 18,21,23,26,30 };
	std::vector> matrix{ row1,row2,row3,row4,row5 };

	matrix[1].erase(matrix[1].begin()+3);
	Solution test;
	std::cout< 
方法二：二叉树查找
 
 
 
 
 
 
 
 
class Solution {
public:
	bool findNumberIn2DArray(std::vector>& matrix, int target) {
		int i = matrix.size() - 1;
		int j = 0;
			while (i >= 0 && j < matrix[0].size() ){
				if (matrix[i][j] > target) i--;
				else if (matrix[i][j] < target) j++;
				else return true;
			}
			return false;
	}
	
};

int main() {
	std::vector row1 = { 1,4,7,11,15 };
	std::vector row2 = { 2,5,8,12,19 };
	std::vector row3 = { 3,6,9,16,22 };
	std::vector row4 = { 10,13,14,17,24 };
	std::vector row5 = { 18,21,23,26,30 };
	std::vector> matrix{ row1,row2,row3,row4,row5 };

	matrix[1].erase(matrix[1].begin()+3);
	Solution test;
	std::cout<