查找概述
l查找——也叫检索,是根据给定的某个值,在表中确定一个关键字等于给定值的记录或数据元素
l关键字——是数据元素中某个数据项的值,它可以标识一个数据元素
l查找方法评价
u查找速度
u占用存储空间多少
u算法本身复杂程度
u平均查找长度ASL(AverageSearchLength):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值叫查找算法的
顺序查找
查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较
算法描述
顺序查找方法的ASL
折半查找
l查找过程:每次将待查记录所在区间缩小一半
l适用条件:必须采用顺序存储结构的有序表
l算法实现
u设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值
u初始时,令low=1,high=n,mid=ë(low+high)/2û
u让k与mid指向的记录比较
u若k==r[mid].key,查找成功
u若k<r[mid].key,则high=mid-1
u若k>r[mid].key,则low=mid+1
u重复上述操作,直至low>high时,查找失败
算法描述
分块查找
查找过程:将表分成几块,块内无序,块间有序;先确定待查记录所在块,再在块内查找
适用条件:分块有序表
算法实现
用数组存放待查记录,每个数据元素至少含有关键字域
建立索引表,每个索引表结点含有最大关键字域和指向本块第一个结点的指针
算法描述
查找方法比较
|
顺序查找
|
折半查找
|
分块查找
|
ASL复杂度
|
最大
|
最小
|
两者之间
|
表结构
|
有序表、无序表
|
有序表
|
分块有序表
|
存储结构
|
顺序存储结构
线性链表
|
顺序存储结构
|
顺序存储结构
线性链表
|
其它查找方法
哈希查找
二叉查找
查找类的实现
Find.java
package datastructure.find;
import datastructure.common.Strategy;
/**
* 查找
* @author luoweifu
*
*/
public class Find {
/**
* 顺序查找
* @param s 要排序的数组
* @param key 关键字
* @return 查找到的下标
*/
public static int arraySearch(int s[], int key) {
for(int i=0; i<s.length; i++) {
if(key == s[i])
return i;
}
return -1;
}
/**
* 折半查找的非递归实现
* @param s 要排序的数组
* @param low 最低点
* @param high 最高点
* @param key 关键字
* @return 查找到的下标
*/
public static int binSearch(int []s, int low, int high, int key) {
while(low <= high) {
int mid = (low + high)/2;
if(s[mid] == key) return mid;
else if(s[mid] > key) high = mid-1;
else low = mid +1;
}
return -1;
}
}
StrategyCompare.java
package datastructure.find;
import datastructure.common.Strategy;
/**
* 比较策略
* @author luoweifu
*
*/
public class StrategyCompare implements Strategy{
public boolean equal(Object obj1, Object obj2) {
// TODO Auto-generated method stub
return false;
}
@Override
public int compare(Object obj1, Object obj2) {
Integer n1 = (Integer)obj1;
Integer n2 = (Integer)obj2;
return n1.compareTo(n2);
}
}
测试
package datastructure.find;
public class Test {
//测试
public static void main(String args[]) {
int a[] = {0,1,2,3,4,5,6,7,8,9};
int n;
n = Find.arraySearch(a, 5);
//n = Find.binSearch(a, 0, 9, 5);
System.out.println(n);
}
}
结果:
5
分享到:
相关推荐
查找问题(顺序查找法, 折半查找法,)基本思想:一列数放在数组a(1)---a(n)中,待查找的数放在x 中,把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标,p初值为1,使x与a(p)比较,如果x不等于a...
区间表(表中每一元素表示的是一个范围的数据)的查找是一个常见的问题,在表的长度较小或要查找元素的数量不多的情况下,折半查找是一种不错并且容易实现的算法。但在某些特殊的行业(如电信业)由于要对长度较大的...
折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)
1、顺序查找法等概率下查找成功时的平均查找长度为(),查找不成功时的比较次数为()。 2、对线性表进行折半查找时,要求线性表必须()。 3、设哈希表L长m=14,哈希函数H(key)=key%11,表中已...... ...........
数据结构习题---折半查找代码 void BinInsert(int A[],int &n,int item) { int j,low=1,high=n,mid; while(low) { /* 利用折半查找法查找合适位置*/ mid=(low+high)/2; /* 计算当前查找部分的中间位置*/ if...
为小于n个关键字设计一个散列表,使得查找成功时平均查找长度,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放定址法的线性探测法处理冲突。 1.从键盘输入关键字个数n及...
合肥工业大学数据结构 查找实验 编写算法实现下列问题的求解。 (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的...
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
实验七 查找 一、实验目的 1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。 3、学会哈希函数的构造方法,处理冲突的机制以及哈希表的查找。 二、实验内容...
折半查找 (1)从键盘输入上述8个整数5 ,14 ,18 ,21 ,23 ,29 ,31 ,35,存放在数组bub[8]中,并输出其值。 (2)从键盘输入21,查找是否存在该数据元素,若存在,则输出该数据元素在表中的位置,否则给出查找失败的...
合肥工业大学数据结构试验七查找 包括完整的实验要求、实验预习报告、实验最终报告 实验要求: <1> 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素(的下标),并以二分查找的判定树来...
实验四 查找 1. 实验目的或任务 通过指导学生上机实践,对常用数据结构的基本概念及其不同的实现方法的理论得到 进一步的掌握,并对在不同存储结构上实现不同的运算方式和技巧有所体会。 2. 实验教学基本要求 1.了解...
由N个有序整数组成的数列已放在一维数组中,给定程序MODI1.C中函数fun的功能是:利用折半查找整数m在数组中的位置。若找到,返回其下标值;反之,返回-1。 折半查找的基本算法是:每次查找前先确定数组中待查的范围...
设计一个程序,建立由有序序列R[0..n-1]进行二分查找产生的判定树,在此基础上完成如下功能: (1) 输出n=11时的判定树并求成功情况下的平均查找长度ASl (2) 通过构造判定树可以求得的成功情况下的平均查找长度...
电脑中往往会出现很重复的文件,有些可能文件名不一样,但内容却是一模一样的,这样会占用大量硬盘空间,本软件针对这一现象,可以查找电脑中文件内容相同的文件(包含文件名不同但内容相同的文件),并且可以计算...
简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。 程序的关键点主要有两点: 1. 如何在页面上表示出查找程序的运行过程。 2. 如何将排序程序的运行...
熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试...
顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)
主要为大家详细介绍了C语言实现顺序表的顺序查找和折半查找,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
1110:查找特定的值 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 26970 通过数: 13296 【题目描述】 在一个序列(下标从1开始)中查找一个给定的值,输出第一次出现的位置。 【输入】 第一行包含一个正整数n,...