欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法(8)——二分查找

程序员文章站 2024-03-17 15:26:04
...

二分查找

将待查找的关键字与有序表的中间位置进行比较,若相等,则查找成功,若小于,则只可能在有序表的前半部分,若大于,则只可能在有序表的后半部分。因此,经过一次比较,可以将查找范围缩小一半。直到找到所需记录或者找不到退出。

查找算法

在长度为n的有序表SL中查找其关键字等于key的记录,若查找成功则返回其在有序表中的位置,若失败则返回哨岗位0。

#include<stdio.h>

typedef int DataType;

int BinarySearch(DataType* SL, DataType key, int n)
{
	int high = n;
	int low = 1;
	int mid;
	
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (key == SL[mid])
		{
			return mid;
		}
		else if (key > SL[mid])
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}

	return 0;
}

int main()
{
	//a[0]是哨岗位,数据从第一个数据单元开始存储
	DataType a[12] = { 0,1,2,3,4,5,6,7,8,9,10,11};
	int num;

	num = BinarySearch(a, 11, (sizeof(a) / sizeof(DataType) - 1));
	if (num == 0)
	{
		printf("fail to locate\n");
	}
	else
	{
		printf("location: %d\n", num);
	}

	return 0;
}

性能分析

查找判定树如下图所示。6号元素需要查找一次,3,9号元素需要查找两次,以此类推。
数据结构与算法(8)——二分查找

以深度为h的二叉树为例,表长n = 2^h -1且各个元素的查找概率相等,平均查找长度为:
数据结构与算法(8)——二分查找

二分查找总结

  1. 查找效率高
  2. 平均查找性能和最坏性能接近
  3. 要求查找表为有序表
  4. 只能用于顺序存储结构(链式存储结构没有地址计算公式,无法随机存取元素)。