天天看点

面试题 -- 有序二维数组的查找

面试题 -- 有序二维数组的查找

vs2010测试通过,代码如下:

/**
*解题思路:
*	题目中给出的二维数组是:从左到右,从上到下依次递增,
	可以从行的最大值 列的最小值 或是 行的最小值 列的最大值 开始查找,
	如果该值大于要查找的数字,则该数值所在的列可以排除,
	如果该数值小于要查找的数字,则该数值所在的行可以排除,
	依次缩小查找的范围,最终得出结果
*以下代码是从行的最大值 列的最小值 开始查找的(即二维数字的右上角的数字)
*/
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#define ROWS 4
#define COLUMNS 4

bool findNumber(int *matrix ,int rows,int columns ,int number);
int _tmain(int argc, _TCHAR* argv[]){
	int arr[ROWS][COLUMNS] ={{1,3,6,9},
					{2,5,9,11},
					{3,7,10,13},
					{4,9,14,22}}; 
	bool isfound;
	int *matrix = &arr[0][0] ;
	isfound = findNumber(matrix,ROWS,COLUMNS,7);
	if(isfound){
		printf("查找成功!");
		system("pause");
		return true;
	}
	printf("查找失败!");
	system("pause");
	return false;
}
bool findNumber(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;
				break;
			}else if(matrix[row*columns + column] > number){
				--column;
			}else{
				++row;
			}
		}
	}
	
	return found;
}
           

继续阅读