二维数组中的查找

二维数组中的查找

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

思路:首先选取数组右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。

1   2   8   9       1   2   8      1  2
2   4   9   12      2   4   9      2  4     2  4
4   7   10  13      4   7   10     4  7     4  7     4  7
6   8   11  15      6   8   11     7  8     7  8     7  8

#include <iostream>
#include <cstdio>
using namespace std;

bool Find(int* matrix, int rows, int columns, int number)
{
    bool found = false;

    if(matrix != nullptr && rows>0 && columns>0)
    {
        int row = 0;
        int column = columns-1;
        while(row<rows && column>=0)
        {
            if(matrix[row*columns + column] == number)
            {
                found = true;
                break;
            }
            else if(matrix[row*columns + column] > number)
            {
                --column;
            }
            else
                ++row;
        }
    }
    return found;
}

// ====================测试代码====================
void Test(char* testname, int* matrix, int rows, int columns, int number, bool expected)
{
    if(testname != nullptr)
        printf("%s begins: ", testname);
    bool result = Find(matrix, rows, columns, number);
    if(result == expected)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}

//  1   2   8   9
//  2   4   9   12
//  4   7   10  13
//  6   8   11  15
// 要查找的数在数组中
void test1()
{
    int matrix[4][4] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
    Test("test1", (int*)matrix, 4, 4, 7, true);
}

void test2()
{
    Test("test2", nullptr, 0, 0, 1, false);
}

int main()
{
    test1();
    test2();

    return 0;
}