搜索二维矩阵（74）

题目

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

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

示例

输入：

matrix = [
  [1,  3, 5, 7],
  [10,11,16,20],
  [23,30,34,60]
]
target = 3

输出：true

输入：

matrix = [
  [1,  3, 5, 7],
  [10,11,16,20],
  [23,30,34,60]
]
target = 13

输出：false

提示

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

算法

双重遍历

const searchMatrix = (matrix, target) => {
	for (let i = 0; i < matrix.length; i++) {
		for (let j = 0; j < matrix[0].length; j++) {
			if (matrix[i][j] === target) return true;
		}
	}
	return false;
};

定位查找

• 如果target小于行末尾元素，那么target可能在这一行
• 如果target大于行内某元素，那么target可能在这个元素左侧

我们从右上角开始先定位行，再在行内向左顺次查找target

我们的结束条件是遍历的行数row大于最大行数或者行内的列数column小于0

const searchMatrix = (matrix, target) => {
	let row = 0,
		column = matrix[0].length - 1;
	while (row < matrix.length && column > 0) {
		if (target > matrix[row][column]) row++;
		else if (target > matrix[row][column]) column--;
		else return true;
	}
	return false;
};

行内二分查找

我们注意到题目中的“递增”条件，想到使用“二分查找”来解题

我们先根据行尾元素来判断target在哪一行，然后因为行内元素递增，所以我们可以使用二分查找在行内查找是否存在对应元素

const searchMatrix = (matrix, target) => {
	let row = 0,
		column = matrix[0].length - 1;
	while (row < matrix.length && target > matrix[row][column]) row++;
	if (row >= matrix.length) return false;
	let start = 0,
		end = column;
	while (start <= end) {
		let m = ~~((start + end) / 2);
		if (matrix[row][m] === target) return true;
		else if (matrix[row][m] > target) end = m - 1;
		else if (matrix[row][m] < target) start = m + 1;
	}
	return false;
};

二分查找

上面的方法我们还可以进行优化：

我们将矩阵的每一行拼接成一个数组，这个数组下标范围是[0, matrix.length * matrix[0].length - 1]，从题目的已知可知整个数组是递增的，我们就可以使用二分查找来检索数据

数组下标的范围就是二分查找的起点和终点，然后我们就可以算出数组中间的那个元素进而进行判断，关键在于我们将数组中第~~(start+end)/2个元素对应到矩阵中——我们将中间的坐标值设为mid，那么对应到矩阵中，这个元素的就在第~~(mid/column)行、第~~(mid%column)列

const searchMatrix = (matrix, target) => {
	const row = matrix.length;
	const column = matrix[0].length;
	let start = 0,
		end = row * column - 1;
	while (start <= end) {
		let mid = ~~((start + end) / 2);
		let midNum = matrix[~~(mid / column)][~~(mid % column)];
		if (midNum === target) return true;
		else if (midNum > target) end = mid - 1;
		else if (midNum < target) start = mid + 1;
	}
	return false;
};