二維數組中的查找，二維數組查找

二維數組中的查找，二維數組查找

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

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

 1 #include "stdafx.h"
 2 #include<stdio.h>
 3 
 4 bool Find(int* matrix, int rows, int columns, int number)
 5 {
 6     bool found = false;
 7 
 8     if(matrix != NULL && rows > 0 && columns > 0)
 9     {
10         int row = 0;
11         int column = columns - 1;
12         while(row < rows && column >= 0)
13         {
14             if(matrix[row*columns + column] == number)
15             {
16                 found = true;
17                 printf("the number %d is in row: %d and column: %d\n", number, row+1, column +1);
18                 break;
19             }
20             else if(matrix[row*columns + column] > number)
21                 -- column;
22             else
23                 ++ row;
24         }
25     }
26 
27     return found;
28 }
29 
30 void Test(char* testName, int* matrix, int rows, int columns, int number, bool expected)
31 {
32     if(testName != NULL)
33         printf("%s begins.\n", testName);
34 
35     bool result = Find(matrix, rows, columns, number);
36     if(result == expected)
37         printf("Passed.\n");
38     else
39         printf("Failed.\n");
40 }
41 
42 void Test1()
43 {
44     int matrix[][4] = {{1,2,8,9}, {2,4,9,12},{4,7,10,13},{6,8,11,15}};
45     Test("Test1", (int*)matrix, 4,4,7,true);
46 }
47 
48 // 1   2   8    9
49 // 2   4   9   12
50 // 4   7   10  13
51 // 6   8   11  15
52 int main()
53 {
54     int rows = 4;
55     int columns = 4;
56     int number = 7;
57     int matrix[][4] = {{1,2,8,9}, {2,4,9,12},{4,7,10,13},{6,8,11,15}};
58     
59     for(int i = 0 ; i < rows; i++)
60     {
61         for(int j = 0 ;j < columns; j++)
62             printf("%d\t", matrix[i][j]);
63         
64         printf("\n");
65     }
66     printf("\n");
67     bool result = Find((int*)matrix, rows, columns, number);
68     if(result)
69         printf("found.\n");
70     else
71         printf("not found.\n");
72     
73     return 0;
74 }