[抄道题] 在二维数组中找某数 - C语言论坛

已结贴√ 问题点数：100 回复次数：2

[抄道题] 在二维数组中找某数

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

    Integers in each row are sorted in ascending from left to right.
    Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [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]
]

Given target = 5, return true.

Given target = 20, return false.

写个高效的算法，查询某值是否存在于 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不存在于上面的矩阵中）

搜索更多相关主题的帖子: efficient　following　example　return　matrix　

第 2 楼

得分:0

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;
}

第 3 楼

得分:0

以下是引用诸葛欧阳在2015-8-11 14:10:28的发言：

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

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