int kthSmallest(int** matrix, int n, int useless, int k) {
//It seems strange that I need ColSize for a n*n matrix...
int small=matrix[0][0], big=matrix[n1][n1], mid, cnt, i, j;
while(small<big) {
mid=small+big>>1;
cnt=0;
j=n1;
for(i=0;i<n;i++) {
while(j>=0&&matrix[i][j]>mid) j;
cnt+=j+1;
}
if(cnt<k) small=mid+1;
else big=mid;
}
return big;
}
20ms C short solution, O(n*log(n))



@zhangyiwei Definitely it's O(n*log(bigsmall)). The maximum comparison times in the inner loop is 2*n
for(i=0;i<n;i++) {
while(j>=0&&matrix[i][j]>mid) j;
cnt+=j+1;
}

