数据结构-查找

几种常见的查找算法

因为查找比较简单,所以我们就用一篇博客大致讲完常用的几种查找算法

认识查找

查找是指根据给定的某个值,在给定的数据结构中查找指定数据元素的过程。若该数据结构中存在指定数据元素,则称查找是成功的,否则认为查找不成功。查找是数据处理领域中的一个重要内容,查找的效率将直接影响到数据处理的效率。

在查找的过程对表做修改操作(如插入和删除),则相应的表称为动态查找表,否则称为静态查找表

逻辑上来说,查找基于的数据结构是集合,集合中的记录之间没有本质关系。但为了获得较高的查找性能,通常将查找集合组织成表、树等结构。

查找运算的主要操作是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个算法效率优劣的标准。

线性表查找

线性表查找是指进行查找运行的查找表所采用的数据结构是线性表的存储结构。关于线性表的相关知识请参考我该系列中线性表部分,这里不做赘述。在线性表查找技术中,对数据元素的查找又分为顺序查找、二分查找和分块查找三种方法。

顺序查找

基本思想:从表的一端开始,顺序扫描线性表,依次将扫描到结点关键字与给定值key进行比较。若当前扫描到的节点关键字与key相等,则查找成功,返回该结点的索引下标;若扫描结束后,仍未找到关键字等于key的结点,则查找失败,返回-1

适用方向:虽然顺序查找的效率不高,但若顺序表为无序表或者采用链式存储结构的线性表,则只能够采用顺序查找。

二分查找

二分查找要求线性表为有序表,即表中结点按关键字有序排列,并且要用顺序表作为表的存储结构。

基本思想:设顺序表存储在有序表data中,这里按照升序排列来讲解规则,设置三个变量lowhighmid,它们分别指向表的当前待查范围的下界、上界和中间位置。初始时,low=0high=n-1,设待查数据元素的关键字为key

(一)令mid = (low + high)/2

(二)比较keydata[mid].key的大小,若相等,则查找成功;若data[mid].key小于key,则表明关键字可能位于mid的右侧,令low=mid+1,上界指示变量high不变;若data[mid].key大于key,则表明关键字可能位于mid的左侧,令high=mid-1,下界指示变量low不变。

(三)比较当前变量lowhigh的值,若low<=high,重复步骤(一)和(二),若low>high,表明整个表查找完毕,线性表中不存在关键字为key的记录,查找失败,返回-1

适用方向:因为二分查找需要线性表有序,而且这种排序过程也需要花费一定的时间,所以二分查找适合于长度较大且经常进行查找的顺序表。

分块查找

分块查找又称为索引顺序查找,是一种性能介于顺序查找和二分查找之间的一种查找方法。

基本思想:分块查找要求把顺序表分成若干块,每一块中的键值存储顺序是任意的,但要求“分块有序”,前一块中的最大键值小于后一块当中的最小键值,即块间结点有序,块内节点无序。另外,还需要建立一个索引表,索引表中的每一项对应顺序表中的一块,索引项由关键字域和链域组成,关键字块存放对应块内结点的最大键值,链域存放对应块首节点的位置。

抽取各块中的最大关键字及其起始位置构成一个索引表,索引表按关键字排序,所以索引表是一个递增有序表。查找时,首先查找索引表,确定待查记录所在块,然后进入已确定的块中进行顺序查找。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//测试数组:数据在运行下面的代码的前提是已经做好顺序块分块排序!
//int[] data = {20,10,30,40,60,45,70,75,90,80,100};
public class LinerListSearch {
//创建索引表结点内部类
static class BlockInfo{
int blockBeginIndex;
int blockEndIndex;
int blockMaxValue;
}
//创建分块查找索引表 创建分块之后进行块与块之间的排序。明天再搞
public BlockInfo[] getBlockArray(int[] data){
int length = data.length;
int n = 4;//(int)Math.sqrt(length);
int m = (int)Math.ceil((length*1.0)/n);
BlockInfo[] blocks = new BlockInfo[m];
for(int i=0;i<m;i++){
BlockInfo block = new BlockInfo();
block.blockBeginIndex = i*n;
if(i*n+n-1 < length-1)
block.blockEndIndex = i*n+n-1;
else
block.blockEndIndex = length-1;
int maxValue = data[block.blockBeginIndex];
for(int j = block.blockBeginIndex;j<=block.blockEndIndex;j++){
if(maxValue < data[j]){
maxValue = data[j];
}
}
block.blockMaxValue = maxValue;
blocks[i] = block;
}
return blocks;
}
//查找
public int blockSearch(int[] data,int key){
System.out.println("key:"+key);
BlockInfo[] blocks = getBlockArray(data);
for(BlockInfo s:blocks){
System.out.println("s.data"+s.blockMaxValue);
}
int blockindex = -1;
for(int i=0;i<blocks.length;i++){
if(key<=blocks[i].blockMaxValue){
blockindex = i;
break;
}
}
if(blockindex!=-1){
int index = blocks[blockindex].blockBeginIndex;
for(;index<=blocks[blockindex].blockEndIndex;index++){
if(key==data[index]){
return index;
}
}
}
return -1;
}
}

分析:如果当前的数据结构能够使用分块查找的话,它的速度要比顺序查找法快,但付出的代价增加辅助存储空间将顺序表分块排序;比二分查找法的速度慢,但优点是不需要对全部记录进行排序。

树查找技术

若想提高动态查找表的效率,可采用特殊的二叉树:二叉排序树作为表的存储结构,因为该数据结构在前面已经介绍过了,所以就不再多说,不清楚的请点击这里:数据结构-二叉排序树

哈希表查找技术

hashCode()作用:计算哈希码,是一个整数,根据哈希码可以计算出数据在哈希表中的存储位置。

equals作用:添加时出现了冲突,需要通过equals进行比较,判断是否相同。查询时也需要equals进行比较,判断是否相同。

未完待续…….

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------