74. 搜索二维矩阵

问题74 搜索二维矩阵 ★☆☆☆☆

https://leetcode-cn.com/problems/search-a-2d-matrix/

这个题目其实就是把一个非递减序列的结构由一维数组换成了二维数组，问题的本质依然是二分查找，先按第一列做二分查找确认target所在行，再按行做二分查找。

	public boolean searchMatrix(int[][] matrix, int target) {
		int row = binarySearch(matrix, target);
		if (row == -1) {
			return false;
		}

		return binarySearch(matrix[row], target);
	}

	private int binarySearch(int[][] matrix, int target) {
		int m = matrix.length;
		int n = matrix[0].length;

		int top = 0, down = m-1;
		while (top <= down) {
			int mid = top + (down-top)/2;
			if (target >= matrix[mid][0] && target <= matrix[mid][n-1]) {
				return mid;
			} else if (target < matrix[mid][0]) {
				down = mid - 1;
			} else if (target > matrix[mid][n-1]) {
				top = mid + 1;
			}
		}

		return -1;
	}

	private boolean binarySearch(int[] row, int target) {
		int left = 0, right = row.length-1;
		while (left <= right) {
			int mid = left + (right-left)/2;
			if (target == row[mid]) {
				return true;
			} else if (target < row[mid]){
				right = mid - 1;
			} else if (target > row[mid]) {
				left = mid + 1;
			}
		}

		return false;
	}

在 LeetCode 查看