面试题3：二维数组中的查找

浏览数：26 / 时间：2015年06月08日

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

当我们需要解决一个复杂的问题时，一个很有效的方法就是从一个简单的具体问题入手，寻找普遍的规律。

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

 1 #include<iostream>
 2 
 3 using std::cout;
 4 using std::endl;
 5 
 6 bool find_num(int *a,int num,int rows,int cols)
 7 {
 8     bool result = false;
 9 
10     if (a!=NULL&&rows>0&&cols>0)
11     {
12         int row = 0;
13         int col = cols-1;
14 
15         while (row < rows&&col >=0)
16         {
17             if (a[row*cols + col ] == num)
18             {
19                 result = true;
20                 break;
21             }
22             else if (a[row*cols + col]>num)
23             {
24                 --col;
25             }
26             else
27             {
28                 ++row;
29             }
30         }
31     }
32 
33     return result;
34     
35     
36 }
37 
38 void Test(char* testName,int *m,int rows,int cols,int num,bool expected)
39 {
40     if (testName!=NULL)
41     {
42         cout << testName << endl;
43     }
44 
45     bool result = find_num(m, num, rows, cols);
46 
47     if (result == expected)
48     {
49         cout << "passed" << endl;
50     }
51     else
52         cout << "failed" << endl;
53 }
54 
55 void Test1()
56 {
57     int matrix[][4] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
58 
59     Test("test1", (int*)matrix, 4, 4, 7, true);
60 }
61 
62 void Test2()
63 {
64     int matrix[][4] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
65 
66     Test("test2", (int*)matrix, 4, 4, 20, false);
67 }
68 
69 void Test3()
70 {
71     
72 
73     Test("test3", NULL, 0, 0, 5, false);
74 }
75 
76 int main()
77 {
78     Test1();
79     Test2();
80     Test3();
81 
82     return 0;
83 }