一个 nxn 的矩阵，矩阵中元素是从左到右顺次增大，从上往下依次增大，编写一个算法，判断某一个数字是不是在这个矩阵中，并且在矩阵中的位置是多少

一个 nxn 的矩阵，矩阵中元素是从左到右依次增大，从上往下依次增大，编写一个算法，判断某一个数字是不是在这个矩阵中，并且在矩阵中的位置是多少？
一个 nxn 的矩阵，矩阵中元素是从左到右依次增大，从上往下依次增大，编写一个算法，判断某一个数字是不是在这个矩阵中，并且在矩阵中的位置是多少？怎么编写程序呢？并计算时间复杂度！

------解决方案--------------------
查找到了范围之后继续递归下去。

引用:

我感觉n*n 的矩阵， 最大的元素是右下角那个，最小的元素是左上角那个。所以先把n×n矩阵分成4个小矩阵 大小是(n/2)  *  (n/2),每个小矩阵的最大值也是右下角，最小值是左上角。通过判断要求的数字是不是在某个小矩阵里面 减小了比较的次数。 时间复杂度应该是O(logn)? 这个不太确定了。。

------解决方案--------------------
沿着斜对角线找
查找x的时候判断   
首先找到第一个使得 X <= Ai,i的那个值i   然后就把矩阵分成3块了(结果不会在右下那一块)
右上的那一块 只需要找 Ai-1,i到Ai-1,n这一行
左下的那一块 只需要Ai,0到Ai,i-1这一行

复杂度是查找n次


------解决方案--------------------
设x=0,y=n-1。初始a[x][y]即为右上角的数，若比要比较的数(设为k)小，则y列比k都大，删掉y列，对应y=y-1;若大,则x行都比k小，删掉x行，对应x=x+1;若等于直接返回。 时间复杂度o(n+n)=o(n)
------解决方案--------------------
写了一个，包括生成矩阵。

#include <time.h>

#include <stdio.h>

#include <vector>


using std::vector;



int max(int l, int r) {

  return l >= r ? l : r;

}


void buildMatrix(vector< vector<int> >* mat, int dim, int maxStep) {


  srand( (unsigned)time( NULL ) );


  for (int r = 0; r < dim; ++r) {

    vector<int> raw;

    for (int c = 0; c < dim; ++c) {

      int step = rand() % maxStep;


      if (r == 0) {

        if (c == 0) {

          raw.push_back(0);

        } else {

          raw.push_back(raw[c - 1] + step);

        }

      } else if (c == 0) {

        raw.push_back((*mat)[mat->size() - 1][c] + step);

      } else {

        raw.push_back(max(raw[c - 1] + step, (*mat)[mat->size() - 1][c]) + step);

      }

    }

    mat->push_back(raw);

  }


}


void showMatrix(const vector< vector<int> >& mat) {


  printf("Num Raws:%d\n", mat.size());

  for (int r = 0; r < mat.size(); ++r) {

    printf("%d:", mat[r].size());

    for (int c = 0; c < mat[r].size() - 1; ++c) {

      printf("%d\t", mat[r][c]);

    }

    printf("%d\n", mat[r][mat[r].size() - 1]);

  }

}


int matrixBinSearch(const vector< vector<int> >& mat,

  int topLeftX, int topLeftY, int botRightX, int botRightY,

  int key) {


  if (topLeftX <= botRightX && topLeftY <= botRightY) {

    int midX = (topLeftX + botRightX) / 2;

    int midY = (topLeftY + botRightY) / 2;


    if (mat[midX][midY] == key) {

      return key;  // 找到

    }


    if (mat[midX][midY] < key) {

      // 在右上找

      int resInTopRight = matrixBinSearch(mat, topLeftX, midY + 1, midX, botRightY, key);

      if (resInTopRight != -1)

        return resInTopRight;


      // 在左下找

      int resInBotLeft = matrixBinSearch(mat, midX + 1, topLeftY, botRightX, midY, key);

      if (resInBotLeft != -1)

        return resInBotLeft;


      // 在右下找

      int resInBotRight = matrixBinSearch(mat, midX + 1, midY + 1, botRightX, botRightY, key);

      if (resInBotRight != -1)

        return resInBotRight;


    } else {

      // 在左上找

      int resInTopLeft = matrixBinSearch(mat, topLeftX, topLeftY, midX - 1, midY - 1, key);