一、查找算法
查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。
二、二分查找算法
1、算法思想
该查找算法又称为 折半查找,二分查找,适合对已经排序好的数据集合进行查找,时间复杂度O(log2n),效率高。
假设有一升序的数据集合,先找出升序集合中最中间的元素,将数据集合划分为两个子集,将最中间的元素和关键字key进行比较,,如果等于key则返回,如果大于关键字key,则在前一个数据集合中查找,否则在后一个子集中查找,直到找到为止,如果没找到则返回-1。
2、二分查找步骤
(1)首先确定整个查找区间的中间位置mid=(low+high)/2;
(2)用待查关键字值与中间位置关键字值进行比较;若相等,则查找成功;
(3)若大于,则在后半个区域中继续进行折半查找。
若小于,则在前半个区域中继续进行折半查找。
(4)查找成功,返回关键字所在数组下标,没找到返回-1;
3、二分查找C语言实现
#include <stdio.h>
#define MaxSize 100
typedef struct
{
int list[MaxSize];
int length;
}Table;
int BinarySearch(Table S, int x);
void main()
{
Table T={{11,22,33,44,55,66,77,88,99},9};
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");
}
int BinarySearch(Table S, int 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)
low= mid+1;
else if(S.list[mid]>x)
high= mid+1;
}
}
参考文献:《The Function and Algorithm of Program Language C/C++》
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)