最近在看查找算法,所以就总结一下:
1、顺序查找(sequential search)是一种最简单的查找方法,一般用于数组。他从顺序表的一端开始依次将每个元素值同给定的值进行比较,若找到则返回该元素所在的下标;否则返回特定值,表示查找失败。时间复杂度O(n)。
对顺序查找算法的一个改进,可在表的尾端设置一个“岗哨”,即在查找之前把给定值x赋给数组a[]中下标为n的元素,这样在循环中就不必进行下标是否越界的检查,当比到下标为n的元素位置时,由于a[n]=x必然成立,则退出循环。即
a[n]=x;
for(int i=0;;i++)
if(a[n].equals(x)) break;
2、二分查找(binary search)又称折半查找。作为二分查找对象的数据必须是顺序存储的有序表,通常假设若关键字是字符或者字符串数据,则按照国际双字节编码(Unicode)有序。
二分查找的过程是:首先取整个有序表的中点元素,同x比较,若小于给定值则在坐子表中,否则在有子表中;这样经过依次查找就将缩短一半的查找空间,直到找到x元素或者当前查找元素为空。
算法描述:
public class testSearch {
public static int binarySearch(Object []a,Object x,int n){
//从数组a的前n个元素中二分查找给定值x
int low=0,high=n-1;
while(low<=high){
int mid=(low+high)/2;
if(((Comparable)a[mid]).compareTo(x)>0)
{
high=mid-1;
System.out.print(a[mid]);
}
else if(((Comparable)a[mid]).compareTo(x)<0){
low=mid+1;
System.out.print(a[mid]);
}
else{
System.out.print(a[mid]);
return mid;
}
}
return -1;//未返回mid则表明查找失败,返回-1
}
public static void main(String[] args) {
Object[]a={1,2,3,4,5,6,7,8,9};
testSearch.binarySearch(a, 1, a.length);
}
}
二分查找过程可用一颗二叉树来描述:树中的每个根节点对应当前查找区间的中点元素a[mid],它的左子树和右子树分别对应该区间的坐子表和右子表,通常把此二叉树称为二分查找的判定树。进行二分查找的二叉树是一颗二叉搜索树,而且是一颗理想平衡树。
二分查找的时间复杂度是O(log2 n)。
3、索引查找(index search)又称分级查找。索引查找是在索引表和主表上进行的查找,过程为:首先根据给定的索引值K1,在索引表上查找索引值等于K1的索引项,以确定对应子表在主表中的开始位置和长度,然后再根据给定值K2,在对应的子表中查找等于K2的元素。对索引表或者子表进行查找时,若表是顺序存储的有序表,则既可以进行顺序查找也可以进行二分查找。
4、分块查找(blocking search)属于索引查找。他要求每个主表中每个子表之间递增有序,即前块中的最大关键字必须小于后块中的最小关键字,但是每个块中的元素排列次序可以是任意的。进行分块查找时,应根据所给的关键字首先查找索引表,从中查找刚好大于等于所给关键字的那个索引项,从而找到待查块,然后再查找这个块,从中顺序查找到相应的记录。
5.散列查找
散列(hash)存储的方法是:以数据集合中的每个元素的关键字k为自变量,通过一种函数h(k)计算出函数值,把这个值用作一块连续存储空间中的元素存储位置(下标)。
构造散列函数的目标是使得散列地址尽可能均匀地分布在散列地址的空间上,同时使得计算尽可能简单,以节省计算时间。常用的散列函数有:
直接定址法 h(k)=k+C;
除留余数法 h(k)=k%m,m是散列长度
数字分析法 取关键字中某些取值较分散的数字作为散列地址的方法。
平方取中法 取关键字平方的中间几位作为散列地址的方法。
折叠法 首先将关键字分割成位数相同的几段(最后一段的位数不足应补0),段的位数取决于散列地址的位数,然后将他们的叠加和作(舍去最高位进位)为散列地址的方法。
从散列表中查找关键字为key的过程就是一个按照查找路径进行顺序查找的过程,若找到则返回相应的元素值,否则返回空值表示查找失败。
6.B树查找
B树是一种具有特殊结构的树,他同二叉树和一般树在结点结构上有所不同。B树分为B-树和B+树。
B_树是一种特殊的多叉树,被称为多路查找树。B_树是一中在数据库和文件系统中最常用的动态索引结构。对于树根节点他最少有两颗子树,最多有m棵子树,对于非树根节点,他最少有m/2向上取整棵子树,最多m棵子树,叶子结点中的子树均为空树;每个节点的关键字个数最少为m/2向上取整-1,最多为m-1个;在B_树的结点结构中,每个关键字域的后面还应包含一个元素引用域,用以存储该关键字所对应元素的引用。
B_树的查找一个关键字K的过程:若B_树非空,首先取出树根结点,使给定值K依次同该结点中的每一个关键字进行比较,直到K<=Ki(假定用Ki作为终止标志,保存比所有关键字都大的一个特定值,该值不妨用MaxKey常量表示)为止,此时若K=Ki,则表明查找成功,返回具有该关键字Ki的记录的存储位置,否则其值为K的关键字只能落在该结点的有Pi-1所指的子树上,接着只要在该子树上继续进行查找即可;这样,每取出一个节点比较后就下移一层,直到查找成功,或被查找的子树为空为止。
public int search(Object k){
int i;
BayerTreeNode p=bt;//将树根指针bt赋给p
while(p!=null){
i=1;
while(((Comparable)k).compareTo(p.key[i])>0)
i++;//用k顺序同节点关键字比较
if(((Comparable)k).compareTo(p.key[i])==0)
return p.rec[i];//查找成功返回记录的存储位置
else
p=p.ptr[i-1];//否则继续向下层节点找
}
return -1;
}
分享到:
相关推荐
几种常用查找算法的比较,内含顺序查找、二分查找、二叉树查找、哈希表查找。
根据自己搜集的资料很实际实用,总结了几种常用的查找算法
几种简单常用的查找算法,饱含binsearch,bstree,Hash,seqsearch。
C#Windows Forms应用演示了通过2D迷宫的几种常见路径查找算法
常见的几种排序方式,包括选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序。vs2008实现,对话框方式,主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集,不能用...
几种常用算法的C语言实现,读者可以直接使用这些算法,方便地进行扩展,为已用。算法有充分的注释,保证读者可以容易地理解。
Java几种常见的排序算法
与好友在网络上相互传输资料时,有时先要知道对方计算机的IP地址,才能与对方建立信息传输通道。...下面,本文就对如何快速、准确地搜查出对方好友的计算机IP地址,提出如下几种方法,相信能对大家 有所帮助!
简单的介绍了一下常用的几种查找与排序技术的程序实现,通过使算法程序化,能够掌握简单的查找与排序方法。
查找方法有很多,本课件,只是列举了几种常用的几种方法
本节主要讲散列表查找实现思想,几种常见散列函数和解决冲突方法。
文档中总结了自己使用过的几种语音的注释符,方便后续学习查找。包括C、Pascal、bat、sql等
同时基于对浏览器console对象的了解产生了一系列之后的问题和分析,对jQuery最常用的三种dom查找方式进行了一个查找效率和性能方面的比较分析。 首先我们要用到的是console.time()和console.timeEnd()这两个成对...
个人积累的Java工具类扩展类,包括字符数组转字符串,质数判断,辗转相除法求最大公约数,对字符串的一些判断,几种常见的数组排序、插入、查找等,闰年判断 日期字符串解析等与日期有关的操作,随机字符串。...
该文档中包含了常见的几种排序方法,其中说明了排序的主要思想和程序源代码,供需要者使用!
对于有的方法,逢用便创建,显得太麻烦不说,无形之中增加了我们的工作量,于是我们可以将常用的一些方法进行封装,以后我们就可以随用随拿啦。 注意: 在封装一个方法之前,我们要先给方法起一个名字,最好是语义...
快捷键是很多软件的常用功能,本文实例讲解了三种方法来实现C# button快捷键,如Alt + *(按钮快捷键),Ctrl+*及其他组合键等。现详述如下: 一、 C# button快捷键之第一种:Alt + *(按钮快捷键) 在大家给button、...
C#Windows Forms应用程序演示了几种常见的遍历2D迷宫的路径查找算法。 用代码做您喜欢的事情,这与我发明这些算法并不一样。 使用Dijkstra,A *,“广度优先”搜索和“深度优先”搜索来查找从A到B的路径。迷宫的...
软件开发必备基础,易学易懂。 教学提示:前几章介绍...教学目标:本章将针对数据的不同组织形式来讨论几种常用的查找方法,用户应学会根据查找算法进行分析,比较各种查找技术的效率,并掌握各种查找算法的使用方法。
[Ctrl+A 全选 注:如需引入外部Js需刷新才能执行] 搜索字符串 查找字串在字符串中的位置 Str.indexOf(subStr) Str代表指定的字符串 subStr表示要搜索的子串 查找指定位置字符 使用str.charAt(n) str 代表要被搜索的...