算法
(二分搜索+分治) $O(log^2n)$
沿着对角线利用二分查找算法查找大于等于target且最小值位置,根据该位置把二维数组分成四份,排除左上角全部小于target,排除右下角全部大于target,还剩下左下角和右上角需要考虑。用相同方法处理子问题。
时间复杂度
一共可以分解为logn个子问题,每个子问题又需要logn来处理,所以时间复杂度$O(log^2n)$
C++ 代码
附上时间对比代码,理论与实践相结合~
#include<cstdio>
#include<Windows.h>
#include <stdlib.h>
const int N =15500;
bool _searchArray(long long array[N][N],int sr,int sc,int er,int ec,int target)
{
//printf("起始行列:%d %d,终止行列:%d %d\n",sr,sc,er,ec);
//if(sr > er || sc > ec) return 0;
int cl = sc ,cr = ec, rl = sr, rr = er;
while ((cl <= cr && rl < rr) || (cl < cr && rl <= rr) )
{
int midc = (cl+cr)>>1,midr = (rl+rr)>>1;
if(cl==cr && rl < rr)
if(array[midr][midc]>=target) rr = midr;else rl = midr+1;
else if(rl == rr && cl < cr)
if(array[midr][midc]>=target) cr = midc;else cl = midc+1;
else
if (array[midr][midc] >= target) {cr = midc,rr = midr;}
else {cl=midc+1,rl=midr+1;}
}
//printf("%d %dvalue:%d,target:%d\n",rl,cl,array[rl][cl],target);
if(array[rl][cl]==target) return 1;
else if(array[rl][cl] < target) return 0;
//答案在rl~n行的0~cl-1列,或cl~m列的0~rl-1行
bool ans1 = false,ans2=false;
if(sc <=cl-1)
ans1 = _searchArray(array,rl,sc,er,cl-1,target);
if (ans1) return ans1;
if (sr <=rl-1)
ans2 = _searchArray(array,sr,cl,rl-1,ec,target);
return ans2;
}
bool searchArray(long long array[N][N], int arrayRowSize, int arrayColSize, int target) {
int cl = 0 ,cr = arrayColSize - 1, rl = 0, rr = arrayRowSize - 1;
if (arrayColSize == 0 || arrayRowSize==0 ) return false;
return _searchArray(array,rl,cl,rr,cr,target);
}
long long array[N][N];
bool otherSearch(long long array[N][N], int arrayRowSize, int arrayColSize, int target){
int i = 0, j = arrayColSize - 1;
while (i < arrayRowSize && j >= 0) {
if (array[i][j] == target) return true;
if (array[i][j] > target) j -- ;
else i ++ ;
}
return false;
}
#include<time.h>
int main()
{
long long k = 0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) array[i][j] = k++;
srand((unsigned)time(NULL));
int s = rand();
s*=s/5;
printf("searching %d in %d*%d\n",s,N,N);
if(searchArray(array,N,N,s) == otherSearch(array,N,N,s))
printf("Two method result is equal~\n");
clock_t start = clock();
for (int i=0;i<=100000;i++)
searchArray(array,N,N,s);
clock_t end = clock();
printf("method1 call 100000 times cost:%fs\n",(double)(end-start)/CLOCKS_PER_SEC);
start = clock();
for (int i=0;i<=100000;i++)
otherSearch(array,N,N,s);
end = clock();
printf("method2 call 100000 times cost:%fs\n",(double)(end-start)/CLOCKS_PER_SEC);
}