算法(二位数组查找)

题目

在一个二位数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二位数组和一个整数，判断数组中是否含有该整数。

最简单的思路：就是遍历数组，找到即可。缺点：时间复杂度比较大
第二种思路：选择中间一个，然后进行判断，左右判断，这样时间复杂度有所减少。
第三种思路：从最右上角开始开始比较，这样每一次都会排出一行或者一列
，这样二位数组的范围逐渐在减少。如下图：

实现

bool find(int *martrix,int rows,int columns,int num){
    int row = 0;
    int column = columns-1;
    if (martrix==NULL||rows<0||column<1) {
        return false;
    }
    while (row<rows&&column<columns) {
        if (martrix[row*columns+column]==num) {
            return true;
        }else if (martrix[row*columns+column]<num){
            ++row;
        }else{
            --column;
        }
    }

    return false;
}

测试

int a[][4] = {{1,2,3,4},{5,6,9,10},{7,12,18,20},{9,13,19,30}};
bool isfind = find(a, 4, 4, 19);
printf("%d\n",isfind);