题目
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:
示例 2:
题解
这种涉及到有序搜索的问题我们很容易想到二分法,那这个是二维的,具体怎么二分呢?先竖着找,再横着找。竖着二分的时候,如果目标值比当前行的第一个大,比当前行的最后一个小,那么再继续横着二分。横着二分就是普通的二分查找了。
java版本
python版本
时间复杂度
O(logM + logN)
领取专属 10元无门槛券
私享最新 技术干货