// 面试题4：二维数组中的查找
// 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按
// 照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个
// 整数，判断数组中是否含有该整数。 #include <cstdio> bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false; if(matrix != nullptr && rows > && columns > )
{
int row = ;
int column = columns - ;
while(row < rows && column >=)
{
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[][] = {{, , , }, {, , , }, {, , , }, {, , , }};
Test("Test1", (int*)matrix, , , , true);
} // 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数不在数组中
void Test2()
{
int matrix[][] = {{, , , }, {, , , }, {, , , }, {, , , }};
Test("Test2", (int*)matrix, , , , false);
} // 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数是数组中最小的数字
void Test3()
{
int matrix[][] = {{, , , }, {, , , }, {, , , }, {, , , }};
Test("Test3", (int*)matrix, , , , true);
} // 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数是数组中最大的数字
void Test4()
{
int matrix[][] = {{, , , }, {, , , }, {, , , }, {, , , }};
Test("Test4", (int*)matrix, , , , true);
} // 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数比数组中最小的数字还小
void Test5()
{
int matrix[][] = {{, , , }, {, , , }, {, , , }, {, , , }};
Test("Test5", (int*)matrix, , , , false);
} // 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
// 要查找的数比数组中最大的数字还大
void Test6()
{
int matrix[][] = {{, , , }, {, , , }, {, , , }, {, , , }};
Test("Test6", (int*)matrix, , , , false);
} // 鲁棒性测试，输入空指针
void Test7()
{
Test("Test7", nullptr, , , , false);
} int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7(); return ;
}