转载自：http://blog.csdn.net/luoweifu/article/details/9272451
查找概述
l 查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素
l 关键字——是数据元素中某个数据项的值，它可以标识一个数据元素
l 查找方法评价
u 查找速度
u 占用存储空间多少
u 算法本身复杂程度
u 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的
顺序查找
查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较
算法描述
顺序查找方法的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
[java]
view plain
copy
package datastructure.find;
import datastructure.common.Strategy;
public class Find {
public static int arraySearch(
int s[],
int key) {
for(
int i=
0; i<s.length; i++) {
if(key == s[i])
return i; }
return -
1; }
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
[java]
view plain
copy
package datastructure.find;
import datastructure.common.Strategy;
public class StrategyCompare
implements Strategy{
public boolean equal(Object obj1, Object obj2) {
return false; }
@Override public int compare(Object obj1, Object obj2) { Integer n1 = (Integer)obj1; Integer n2 = (Integer)obj2;
return n1.compareTo(n2); } }
测试
[java]
view plain
copy
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); System.out.println(n); } }
结果：
5
