百度笔试题：在矩阵中查找k

题目：

给定如下的n*n的数字矩阵，每行从左到右是严格递增， 每列的数据也是严格递增

1 2 3

3 5 6

4 8 9

现在要求设计一个算法， 给定一个数k 判断出k是否在这个矩阵中。 描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

 

答案：

沿着矩阵的对角线进行二分查找。如果k在这条对角线上，则可以得出，k在矩阵中；如果k比对角线上第一个数小，或者比对角线上最后一个数大，则可以得出，k不在矩阵中；否则，根据二分查找算法可以得出k在对角线上相邻的两个数之间，从而可以通过这两个相邻的数确定左下矩阵和右上矩阵，对这两个矩阵递归调用上述算法。