查找算法2——折半查找

从小到大排列的有序序列。折半查找的算法描述如下：

将待查找元素与表中间的元素进行比较，如果两者相等，则说明查找成功；否则利用中间位置将表分成两部分，如果待查找元素小于中间位置的元素值，则继续与前一个子表的中间位置元素记性比较；否则与后一个子表的中间位置元素进行比较。不断重复上述操作，直到找到与待查找元素相等的元素，表明查找成功。如果子表为空表，表明查找失败。

【示例】

一个有序顺序表为7，15，22，29，41，55，67，78，81，99，如果要查找的元素为67。利用折半查找算法思想，过程如下。

其中low，high，表示两个指针，分别指向待查找元素的下界和上界，指针mid指向low和high的中间位置，即mid=(low+high)/2。

初始时，low=0,high=9,mig=(0+9)/2=4,因为list[mid]<x，座椅需要在右半区继续寻找。此时low=5,high=9,mid=(5+9)/2=7,因为list[mid]>x，所以需要在左半区继续查找x。此时有low=5,high=6,mid=5，因为list[mid]<x，所以需要在右半区继续找，此时有low=6,high=6,mid=6，list[mid]=x，查找成功。

#include<stdio.h>
#include<iostream>

#define MaxSize 100
using namespace std;
typedef struct
{
	int list[MaxSize];
	int length;
}Table;
int BinarySearch(Table S, int x);
void main()
{
	Table T = { { 12,24,36,48,60,72,84,96 },8 };
	int i, find, x;
	printf("有序顺序表中的元素:\n");
	for (i = 0; i<T.length; i++)
		printf("%4d", T.list[i]);
	printf("\n请输入要查找的元素:");
	scanf("%d", &x);
	find = BinarySearch(T, x);
	if (find)
		printf("元素%d是顺序表中的第%d个元素.\n", x, find);
	else
		printf("没有找到该元素.\n");

	system("pause");
}
int BinarySearch(Table S, int x)
/*在有序顺序表中折半查找元素x*/
{
	int low, high, mid;
	low = 0, high = S.length - 1;			/*设置待查找元素范围的下界和上界*/
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (S.list[mid] == x)		/*如果找到元素，则返回该元素所在的位置*/
			return mid + 1;
		else if (S.list[mid]<x)	/*如果mid所指示的元素小于x，则修改low指针*/
			low = mid + 1;
		else if (S.list[mid]>x)	/*如果mid所指示的元素大于x，则修改high指针*/
			high = mid - 1;
	}
	return 0;
}

 

结果：

【特点】
*折半查找算法要求待排序的元素必须是一个有序的序列。
*折半搜索查找的算法效率优于顺序查找算法的效率。

【效率分析】

折半查找算法过程可以用一个判定树去描述。例如用折半查找值为56的元素时，需要比较4次。从图中可以看出查找值为41的元素时，需要比较1次。查找值为78的元素时，需要比较2次。查找值为55的元素时，需要比较3次。查找值为67的元素时，需要比较4次。整个查找过程可以用二叉判定树来表示。

其中结点旁边的序号为该元素在序列中的下标。从图中的判定树不难看出，查找元素67的过程正好是从根结点到元素值为67的结点路径。查找元素67的比较次数正好是该元素在判定树种所在层次。因此，如果表中有n个元素，折半查找成功时，最多需要比较的次数为。

对于具有n个结点的有序表（恰好构成一个深度为h的满二叉树）来说，有，二叉树中第i层的结点个数是。假设表中每个元素的查找概率相等，即，则有序表在折半查找成功时的平均查找长度为：

查找失败时，有序表的折半查找失败平均查找长度为