二維數組中的查找

題目:在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

思路:這題和堆排序有類似，查找過程中從右上方的數字開始，如果該數字比查找的數字小，那麼該數字所在行可以刪除，不用繼續考慮；如果該數字比查找的數字大，那麼該數字所在列可以刪除。這樣，每次執行，都會刪除一行或者一列，極端情況下，執行2n次。

#include "stdafx.h"
#include<stdio.h>

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

if(matrix != NULL && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while(row < rows && column >= 0)
{
if(matrix[row*columns + column] == number)
{
found = true;
printf("the number %d is in row: %d and column: %d\n", number, row+1, column +1);
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 != NULL)
printf("%s begins.\n", testName);

bool result = Find(matrix, rows, columns, number);
if(result == expected)
printf("Passed.\n");
else
printf("Failed.\n");
}

void Test1()
{
int matrix[][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);
}

// 1 2 8 9
// 2 4 9 12
// 4 7 10 13
// 6 8 11 15
int main()
{
int rows = 4;
int columns = 4;
int number = 7;
int matrix[][4] = {{1,2,8,9}, {2,4,9,12},{4,7,10,13},{6,8,11,15}};

for(int i = 0 ; i < rows; i++)
{
for(int j = 0 ;j < columns; j++)
printf("%d\t", matrix[i][j]);

printf("\n");
}
printf("\n");
bool result = Find((int*)matrix, rows, columns, number);
if(result)
printf("found.\n");
else
printf("not found.\n");

return 0;
}