C/MFC 折半查找(二分查找)

分治的思想
服务器君一共花费了229.975 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

折半查找的前提是已经对数据做好了排序,然后再折半查找。例如排序后的数据是1 5 12 35 64 78 89 123 456。你要查找12,首先用12跟上面排好顺序的9个数中间那个比较(64),12 < 64,因此你查找的数据在前半部分,即 1 5 12 35 64,再用12跟前半部分中间那个数比较(12),这样找了2次就找到了。

折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。折半查找的目的是提高查找的效率。

C语言的函数实现如下:

int binsearch(int x, int v[], int n)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if(x < v[mid])
			high = mid - 1;
		else if (x > v[mid])
			low = mid + 1;
		else
			return mid;
		// 看看循环执行了多少次
		//printf("mid = %d, low = %d, high = %d n", mid, low, high);
	}
	return -1;
}

MFC运行结果:

MFC 程序如下:

char tmp[10] = "";
int rand_num[10];
CString str[10];
CString result;
CString sort_result;

void CNM_MFCDlg::OnBnClickedOk()
{
	CEdit* pBoxOne;
	pBoxOne = (CEdit*) GetDlgItem(IDC_EDIT1);

	srand((unsigned)time(NULL));
	for(int x=0; x < 10; x++)
	{
		rand_num[x] =  rand()0;
		str[x] = itoa(rand_num[x],tmp,10);
		result = result + str[x] + _T(" ");
	}

	pBoxOne-> SetWindowText( result );
	//MessageBox(str,_T("程序运行结果"),MB_OK);
	result.ReleaseBuffer();
}

void CNM_MFCDlg::OnBnClickedButton1()
{
	CEdit* pBoxTwo;
	pBoxTwo = (CEdit*) GetDlgItem(IDC_EDIT2);
	selection_sort(rand_num,10);

	for(int x=0; x < 10; x++)
	{
		str[x] = itoa(rand_num[x],tmp,10);
		sort_result = sort_result + str[x] + _T(" ");
	}

	sort_result = sort_result + _T("~ rn");
	//UpdateData(false);
	pBoxTwo-> SetWindowText( sort_result );
	sort_result.ReleaseBuffer();
}


void CNM_MFCDlg::OnBnClickedButton2()
{
	CEdit* pBoxThree;
	pBoxThree = (CEdit*) GetDlgItem(IDC_EDIT3);
	CString searchNum;
	CString showStr;
	char tmp[10] = "";
	//selection_sort(rand_num,10);

	pBoxThree -> GetWindowText(searchNum);

	int srh_n = _ttoi(searchNum);

	int result = binsearch(srh_n, rand_num, 10);
	showStr = itoa(result,tmp,10);

	MessageBox(searchNum + _T("所在数组的下标为") + showStr,_T("程序运行结果"),MB_OK);
}

void CNM_MFCDlg::OnBnClickedCancel()
{
	CDialogEx::OnCancel();
}

void selection_sort(int *a,int n)
{
	int i,j,s;
	for(i=0; i < n-1; i++)
	{
		s=i;
		for(j=i+1; j < n; j++)
		{ 
			if(a[j] < a[i])
			{
				s=j;
			}
		}
		swap(&a[i],&a[s]);
	}
}

void swap(int *p1,int *p2)
{
	int temp;
	temp=*p1;
	*p1=*p2;
	*p2=temp;
}

int binsearch(int x, int v[], int n)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if(x < v[mid])
			high = mid - 1;
		else if (x > v[mid])
			low = mid + 1;
		else
			return mid;
		// 看看循环执行了多少次
		//printf("mid = %d, low = %d, high = %d n", mid, low, high);
	}
	return -1;
}

记得在头文件声明函数。

将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x < a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。

二分搜索法的应用极其广泛,而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定,正确地归纳奇偶数的各种情况,其实整理后可以发现它的具体算法是很直观的。

刚开始的时候数组时排好顺序的:从小到大,或者从大到小。然后将这个数组折中,用中间的这个数和要查找的数比较大小。例如:如果我从小到大,我将数组这种后,用中间的数和要查找的数比较,如果小,则那个要查找的数绝对在中间靠左的范围里,如果大,则那个要查找的数绝对在中间靠右的范围里,然后同理,慢慢慢慢缩小范围,知道查找到为止。

本文地址:http://www.nowamagic.net/librarys/veda/detail/551,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/551

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编程之美:微软技术面试心得》 《编程之美》小组 (作者)

《编程之美:微软技术面试心得》是一本让人着迷的书!阅读起来。有些题目的内容会引起强烈的共鸣,尤其是那些自己非常熟悉并且又深知解答的题目;也有一些题目让我异常惊诧,原来除了我所知道的解答思路之外,还有更好的解答以及更深层次的原因。还有一些题目是从来没想到过的。阅读过程是一次愉快的享受,也是脑细胞持续活跃的过程。

更多计算机宝库...