力扣hot100 搜索二维矩阵 II 二分 抽象BST-???? 二分

????‍???? 参考思路
⏰ 时间复杂度: $O(n\log n)$
???? 空间复杂度: $O(1)$

class Solution {
	public boolean searchMatrix(int[][] matrix, int target)
	{
		int n = matrix.length;
		int m = matrix[0].length;
		if (n == 0 || m == 0)
			return false;
		for (int i = 0; i < n; i++)
		{
			if (matrix[i][0] > target)
				break;
			if (matrix[i][m - 1] < target)
				continue;
			int col = bsearch(matrix[i], target);
			if (matrix[i][col] == target)
				return true;
		}
		return false;
	}

//	在 a 中二分查找 x，没找到返回 -1
	private int bsearch(int[] a, int x)
	{
		int l = 0;
		int r = a.length - 1;
		while (l < r)
		{
			int m = l + r >> 1;
			if (a[m] >= x)
				r = m;
			else
				l = m + 1;
		}
		return l;
	}
}