算法:二分
思路与算法
我们可以看到这里的二维数组,对于每一行,都是绝对有序的。所以,我们可以对每一行进行二分查找。若找到,return true
;若没找到,进行下一层的寻找。若到结尾行没有找到,return false
。
注意:事先判断数组大小。若行数为$0$直接
return false
。
代码
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
int n = array.size();
if (!n)
return false;
int m = array[0].size();
int l = 0, r = m - 1;
for (int i = 0; i < n; i++)
{
l = 0, r = m - 1;
while (l <= r)
{
int mid = l + r >> 1;
if (array[i][mid] == target)
return true;
else if (array[i][mid] < target)
l = mid + 1;
else
r = mid - 1;
}
}
return false;
}
};
复杂度分析
空间复杂度:$O(mn)$,其中$n$为数组行数,$m$为数组列数;
时间复杂度:$O(m\log_2 n)$,$m$和$n$定义同上