现在的位置: 首页 > 综合 > 正文

0904_两个小题目_二分查找和杨氏矩阵查找

2013年08月15日 ⁄ 综合 ⁄ 共 1033字 ⁄ 字号 评论关闭

二分查找:

十分简单,但编程珠玑上的说不要掉以轻心,so,写下来,以防万一:
int binary_search(int* a, int low, int high, int Num)
{
	if(low > high)
		return -1;
	int middle = (low + high)/2;
	if(Num == a[middle])
		return middle;
	else if(Num > a[middle])
		binary_search(a, middle + 1, high, Num);
	else
		binary_search(a, low, middle - 1, Num);

}

杨氏矩阵查找问题:
     在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 
     例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字 6,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。 
我直接实现的是方法 2、首先直接定位到最右上角的元素,再配以二分查找,比要找的数(6)大就往左走,要找数(6)的小就往下走,直到找到要找的数字(6)为止,如下图所示: 
//代码
#define  COL 4
#define  ROW 4
bool young_matrix_search(int array[][COL], int Num)
{
	int i = 0, j = COL-1;
	while(i >= 0 && i <= ROW - 1 && j >= 0 && j <= COL - 1)
	{
		if(array[i][j] == Num)
			return true;
		if(array[i][j] > Num)
			j--;
		if(array[i][j] < Num)
			i++;

	}
	return false;

}
#include <iostream>
using namespace std;
int main()
{
	//int a[] = {1,3,5,7,9,12,45};
	//binary_search(a, 0, sizeof(a)/sizeof(a[0]) - 1, 55);

	int a[ROW][COL] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
	for (int i = 1; i <= 15; i++)
	{
		if (young_matrix_search(a, i))
			cout<<"search:"<<i<<" hit!"<<endl;
		else
			cout<<"search:"<<i<<" miss!"<<endl;
			
	}
	
}

抱歉!评论已关闭.