C/MFC折半查找（二分查找）

折半查找的前提是已经对数据做好了排序，然后再折半查找。例如排序后的数据是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])
			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  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。

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

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

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