查找,最天真无邪的方法就是linearSearch:将给定的数组arr从头至尾扫描一遍
int linearSearch(int arr[],int n,int x)
{
int i;
for(i=0;i<n;i++)
{
if(x==arr[i])
return i;
}
return -1;
}
毫无疑问,该算法的时间复杂度为O(n).
另外,倘若所给的是一个有序的数组arr,那么我们可以考虑折半查找:
1) 将待查找元素x与arr中间元素比较
2) 相等则返回index
3) 小于则抛弃右半部分
4) 大于则抛弃左半部分
这是递归实现的版本
int binarySearch(int arr[],int l,int r,int x)
{
if(l<=r)
{
int mid=(l+r)/2;
if(x==arr[mid])
{
return mid;
}else if(x<arr[mid])
{
return binarySearch(arr,l,mid-1,x);
}else{
return binarySearch(arr,mid+1,r,x);
}
}
return -1;
}
这是循环迭代实现的版本
int binarySearch2(int arr[],int l,int r,int x)
{
int mid;
while(l<=r)
{
mid=(l+r)/2;
if(x==arr[mid])
{
return mid;
}else if(x<arr[mid])
{
r=mid-1;
}else{
l=mid+1;
}
}
return -1;
}
折半查找的时间复杂度为O(Logn).
还有一种内插搜索算法,它的平均时间复杂度为O(LogLogn),但最坏情况是O(n).
int interpolationSearch(int arr[],int n,int x)
{
int l=0;
int r=n-1;
int m;
while(arr[r]!=arr[l]&&x>=arr[l]&&x<=arr[r])
{
m=l+((x-arr[l])*(r-l)/(arr[r]-arr[l])); /*这里应该是数学家讨论的问题*/
if(arr[m]<x)
{
l=m+1;
}
else if(x<arr[m])
{
r=m-1;
}
else
{
return m;
}
}
if(x==arr[l])
{
return l;
}
else{
return -1;
}
}
<!--EndFragment-->
相关推荐
查找算法比较.docx
比较在有序表和无序表下进行顺序查找时的效率 表中的奇数从1开始一共n个,要查找searches次 1.生成新的有序表 2.生成新的无序表 3.测试查找有序表的效率 4.测试查找无序表的效率 比较在同一有序表下进行顺序查找...
几种常用查找算法的比较,内含顺序查找、二分查找、二叉树查找、哈希表查找。
排序和查找算法速度排序和查找算法速度排序和查找算法速度排序和查找算法速度
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法静态查找表。实现有序表的折半查找算法
二分查找算法,二分查找算法课件,二分查找算法PPT
写出二分查找算法。给出一组有序的测试数据例如:1,3,4,7,8 查找有无3
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契...
二叉查找与递归二叉查找算法
常用排序查找算法详解:各种排序查找算法
区间表(表中每一元素表示的是一个范围的数据)的查找是一个常见的问题,在表的长度较小或要查找元素的数量不多的情况下,折半查找是一种不错并且容易实现的算法。但在某些特殊的行业(如电信业)由于要对长度较大的...
各种查找算法性能比较 ①静态查找 折半查找和斐波拉契查找(有序) ②动态查找 二叉排序树的基本操作 任务: 编写算法实现对依次输入的关键字序列建立二叉排序树 并能实现二叉排序树的查找 插入和删除运算 ...
顺序查找算法C语言源程序,顺序查找算法比较简单,即从数据序列的第一个元素开始,进行一一匹配操作,匹配成功则返回匹配结果。
二叉排序树:更新二叉排序树、查找结点、插入结点、删除结点、中序输出排序树 、返回 查找算法:顺序查找、二分查找、二插排序树、返回
查找算法授课ppt,包含基础的查找算法的概念介绍和C语言编程时间的简单展示
该算法是在折半算法的基础上,推广折段的段数,通过简单的数学模型证明了最优的分段数为3,而不是2(即折半)。在文章的最后给出了算法的C程序代码。如果有应用到实际中,算法还可以进一步精简。
java 几种查找算法
折半查找算法,折半查找算法,折半查找算法