写个高效的算法，查询某值是否存在于 m*n 的二维数组中。这个二维数组具有如下特征：
a. 每行的整型值是递增的
b. 每列的整型值也是递增的
例如
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定值5，返回true （表示5存在于上面的矩阵中）
给定值20，返回false （表示20不存在于上面的矩阵中）

先用二分查找定位到刚好小于target的行，本例中是第3行，然后再从[0,3)行中二分查找target：

#include <stdio.h>
#include <stdlib.h>

#define M 5
#define N 5

int compare(const void *p1, const void *p2)
{
    return *(int*)p1 - *(int*)p2;
}

int main(void)
{
    int target;
    scanf("%d", &target);
    int matrix[M][N] =
    {
        {1,   4,  7, 11, 15},
        {2,   5,  8, 12, 19},
        {3,   6,  9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30}
    };
    int low = 0, high = M, mid = 0;
    while (low < high)
    {
        mid = (low + high)/2;
        if (matrix[mid][0] < target)
            low = mid + 1;
        else
            high = mid;
    }
    bool found = false;
    for (int row = 0; row < high; ++row)
    {
        if (bsearch(&target, matrix[row], N, sizeof(int), compare))
        {
            found = true;
            break;
        }
    }
    puts(found ? "true" : "false");
    return 0;
}

期待大神更好的算法。。。

还是二分法，沿数组的斜对角找
比如找16， 可以定位到9，17之间
9左上，17右下的全部是
对左下和右上再递归

kenierlee 和 实际应用 的算法不错，但还是不够高效。
可以从右上角开始，亦不使用二分查找。

我先抛砖引玉

#include <stdio.h>
#include <stdbool.h>

bool search_matrix( size_t, size_t, const int matrix[*][*], int );

int main( void )
{
    const int matrix[][5] =
    {
        { 1,   4,  7, 11, 15 },
        { 2,   5,  8, 12, 19 },
        { 3,   6,  9, 16, 22 },
        { 10, 13, 14, 17, 24 },
        { 18, 21, 23, 26, 30 }
    };
    const size_t m = sizeof(matrix)/sizeof(matrix[0]);
    const size_t n = sizeof(matrix[0])/sizeof(matrix[0][0]);

    // 测试
    puts( search_matrix(m,n,matrix,5) ? "true" : "false" );
    puts( search_matrix(m,n,matrix,20) ? "true" : "false" );

    return 0;
}

bool search_matrix( size_t m, size_t n, const int matrix[m][n], int target )
{
    for( size_t r=0, c=n-1; r<m && c<n; )
    {
        if( matrix[r][c] == target )
            return true;
        else if( matrix[r][c] < target )
            ++r;
        else if( matrix[r][c] > target )
            --c;
    }
    return false;
}

你这样也是逐行排查先确定行，再逐列确定再那一列，就效率而言不如先用而纷纷确定行再用二分法确定列

根据行列递增的特点，逐步缩小范围，首先在首行和首列中查找小于或等于查找值的行或列，舍去大的部分，再在尾行和尾列中查找大于或等于查找值的行或列，舍去小的部分，循环处理，直到剩下一个元素，比对。
#include <stdio.h>
int data[5][6] =
    {
        {1,   4,  7, 11, 15,25},
        {2,   5,  8, 12, 19,28},
        {3,   6,  9, 16, 22,31},
        {10, 13, 14, 17, 24,32},
        {18, 21, 23, 26, 30,39}
    };
 int   m=5,n=6;
 int main()
{
 int x;
 int f(int);
 while(x!=-1)
 {
 scanf("%d",&x);
 printf("%s\n",(f(x)==1)?"true":"false");
            
 }
}
 int f(int x)
 {
  int si,sj,ei,ej;
  int s,e,k;
  si=0;
  sj=0;
  ei=m-1;
  ej=n-1;
  while((ei-si>0)|(ej-sj>0))
  {
      if(data[si][sj]>x) return 0;
    //用二分查找在首行中查找<=x的列号      
      s=sj;
      e=ej;
      if(data[si][e]<=x) s=e;
    while(e-s>1)
      {
          k=s+(e-s)/2;
          if (data[si][k]>x) e=k;
          else s=k;
      }
    ej=s;//更改尾列下标，缩小范围
      //用二分查找在首列中查找<=x的行号
    s=si;
      e=ei;
      if(data[e][sj]<=x) s=e;
    while(e-s>1)
      {
          k=s+(e-s)/2;
          if (data[k][sj]>x) e=k;
          else s=k;
      }
       ei=s;//更改尾行下标，缩小范围
        
    if(data[ei][ej]<x) return 0;
   
    //用二分查找在尾行中查找>=x的列号      
      s=sj;
      e=ej;
      if(data[ei][s]>=x) e=s;
    while(e-s>1)
      {
          k=s+(e-s)/2;
          if (data[ei][k]<x) s=k;
          else e=k;
      }
      sj=e;//更改首列下标，缩小范围
      //用二分查找在尾列中查找>=x的行号  
    s=si;
      e=ei;
      if(data[s][ej]>=x) e=s;
    while(e-s>1)
      {
          k=s+(e-s)/2;
          if (data[k][ej]<x) s=k;
          else e=k;
      }
      si=e;//更改首行下标，缩小范围
  }
 return data[si][sj]==x;//此时si=sj,ei=ej
 }

“先用二分确定行再用二分法确定列” --- 问题是，你用二分不能确定行呀
我的算法在最差情况下也只需要用 target 和 matrix[m][n]中m+n个元素 比较一下，肯定比二分快

把“if( matrix[r][c] > target )”去掉看着更清爽些