二维数组中的查找

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include <exception>
 4 using namespace std;
 5 
 6 /*二维数组中的查找*/
 7 /*
 8 题目:
 9 在一个二维数组中,每一行都按照从左到右递增的顺序排序,
10 每一列都按照从上到下递增的顺序排序.请完成一个函数,
11 输入这样的一个二维数组和一个整数,
12 判断数组中是否含有该整数.
13 */
14 bool FindNumber(int *matrix,int columns,int rows,int key)
15 {
16     bool found = false;
17     if(matrix != NULL && columns > 0 && rows > 0)
18     {
19         int row = 0;
20         int column = columns-1;
21         while(column>=0 && row<rows)
22         {
23             if(matrix[row*columns+column] == key)
24             {
25                 found = true;
26                 break;
27             }
28             else if(matrix[row*columns+column] > key)
29             {
30                 column--;
31             }
32             else
33             {
34                 row++;
35             }
36         }
37     }
38     return found;
39 }
40 
41 int _tmain(int argc, _TCHAR* argv[])
42 { 
43     int matrix[]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};
44     int columns = 4;
45     int rows = 4;
46     cout<<FindNumber(matrix,columns,rows,12);
47     return 0 ;
48 }

规律:选取右上角的数字。如果等于,查找结束,如果大于,去掉该数字所在的列，如果小于，去掉这个数字所在的行.