关于2维数组的查找， 时间复杂度

Question

GS， XDJM们，
想请问的问题是：我有两个2D数组，想在里面找出一个数字，它不是只有一个的。一个是每行的数字为递增，而每列的数字没有任何顺序，那么我写的算法是：
for{ binary search（每行的数字）} 时间复杂度是：　n*log2nanother: 行，列的数字都是已经按递增的顺序排列好，那么我想同时都ＢＩＮＡＲＹ　ＳＥＡＲＣＨ行和列的数字，　时间复杂为　log2n*log2n我应该怎么写呢？　另外，请给点指点，关于时间复杂度有错误吗？

Answer 1

第一个可以先匹配所有的a[i][0]和a[i][length-1],确定哪些行里面肯定不会有!
这一个时间复杂度应该是n*log2n,第二个可以在二维上二分法确定范围如每次比较a[(length1-1)/2][(length2-1)/2]
时间复杂度,应该是log2n2=2*log2n

Answer 2

为什么第二个是log2n2呢？ 这个是不是等于 log2n + log2n ？第二个的意思我还不太明白。 是在行列上都用二维查找，但是在程序流程上应该怎么实现呢？

Answer 3

因为第二个，可以先在第一行上确定范围，时间复杂度为log2n。而这时候列已经为唯一[见说明]，只要在一列上搜索，列时间复杂度为log2n，所以总共为log2n+log2n。说明：如第一行判断a[0][j]<n<a[0][j+1],则n确定为在a[][j]列，只要判断这一列。

Answer 4

上面的a[0][j]<n<a[0][j+1]应为a[0][j]<=n<a[0][j+1]。