一、简介
查找(Searching): 就是根据给定的某个值,在查找表中确定⼀一个其关键字等于给定值 的数据元素
查找表(Search Table)是由同⼀一类型的数据元素(记录)构成的集合
关键字(Key)是数据元素中某个数据项的值.⼜又称为键值. ⽤用它可 以表示⼀一个数据元素,也可以标识⼀一个记录的某个数据项(字段). 我们称为关键码
若关键字可以唯⼀一地标识⼀一个记录, 则称此关键字为主关键字 (Primary Key)
对于那些可以识别多个属于元素(记录)的关键字,我们称为次关键 字(Secondary Key)
1.1查找表操作方式分类
-
静态查找表(Static Search Table): 只作查找操作的查找表; 1.查询某个”特定的”数据元素是否在查找表中;
-
检索某个"特定的"数据元素和各种属性;
动态查找表(Dynamic Search Table): 在查找过程中同时插⼊入查找表中不不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作 -
查找时插⼊入数据元素;
-
查找时删除数据元素;
二、顺序表查找
2.1 普通顺序查找
int Sequential_Search(int *a,int n,int key){
for (int i = 1; i <= n ; I++)
if (a[i] == key)
return I;
return 0;
}
2.2 哨兵查找
我们在上面的顺序查找中每次都要判断i<n,那么我们能不能每次不用判断，而只需要判断a[i]是否等于key值呢？我们可以把数组a[0]空出来，存入key值，在比对的过程中如果中途找到则存在，如果返回最后找到说明比对的是我们的哨兵，说明数组中不存在。
int Sequential_Search2(int *a,int n,int key){
int I;
//设置a[0]为关键字值,称为'哨兵'
a[0] = key;
//循环从数组尾部开始
i = n;
while (a[i] != key) {
I--;
}
//返回0,则说明查找失败
return I;
}
三、折半查找与变体
折半查找与变体需要数据是有序的,其核心思想都是缩小查找范围进行查找。
3.1 折半查找
每次都比较中间值与查找值的关系确定下一次比对的范围，每次都是一半。
int Binary_Search(int *a,int n,int key){
int low,high,mid;
low = 1;
high = n;
while (low <= high) {
mid = (low + high) /2;
if (key < a[mid]) {
high = mid-1;
}else if(key > a[mid]){
low = mid+1;
}else
return mid;
}
return 0;
}
3.2 插入查找
如果数据分布是一致的，我们可以使用插值查找，差值查找的中间值为（key - a[low]）/(a[high] - a[low])即位查询值在整体位置的偏移量。
//插值查找
int interpolationSearch(int *a,int n,int searchKey)
{
int low = 1,high = n,mid = 0;
while (low <= high) {
mid = low+(high-low)*(searchKey-a[low])/(a[high]-a[low]);
if(a[mid] < searchKey)
{
low = mid+1;
}
else if(a[mid] > searchKey)
{
high = mid-1;
}
else
{
return mid;
}
}
return 0;
}
3.3 斐波那契查找
1、斐波那契查找就是在二分查找的基础上根据斐波那契数列分割的，在斐波那契数列找一个等于略大于待查找表长度的数f(k),待查找表长度扩展为f(k)-1(如果原来数组长度不够f(k)-1，则需要扩展，扩展时候用原待查找表最后一项填充),mid = low + f(k-1) -1,已mid为划分点，将待查找表划分为左边，右边* 划分图示
斐波那契查找
2、划分原因
斐波那契数列 f(k) = f(k - 1) + f(k -2)
假如待查找数组长度为f(k),不考虑mid的情况下，左边为f(k - 1),右边为f(k -2),考虑mid的情况下要不左边是f(k-1) - 1或者右边是f(k - 2) - 1，逻辑不好写
如果待查找长度为f(k) - 1，mid = low + (f(k - 1) - 1)则不存在这样的问题
int fibSearch(int[] arr,int key)
{
int left=0; //初始指向最数组最左边
int right=arr.length-1; //初始指向最数组最右边
int k=0; //指示斐波那契数列的下标，初始为0是为了根据数组长度确定数组需要扩展的长度
int mid=0; int[] f=fib(); //获取斐波那契数列
while (arr.length>f[k]-1){ //这里的f[k]是arr距离斐波那契数列最近的数值，为什么-1，为了符合数组特性(数组最大元素下标是数组长度-1)
k++;
}
int[] temp=Arrays.copyOf(arr,f[k]); //为什么构建一个新数组，因为下面需要对数组进行扩展，查找最后还要用到原始数组，所以不能用原始数组 //扩展数组
for (int i=right+1;i<temp.length;i++){ //这里为什么用temp.length?因为上面 Arrays.copyOf(arr,f[k])已经对数组扩展了，这里我们进行的是把扩展的值都改为原始数组的最大值
temp[i]=arr[right];
}
while (left<=right){
mid=left+f[k-1]-1; //这里就是为mid确定位置，位置确定请看上面的图
if (key<temp[mid]){ //如果当前mid值大于key，说明key在mid左边部分，继续对左边的 F[k-1]-1部分进行分割
right=mid-1;
k--;
else if (key>temp[mid]){
left=mid+1;
k-=2;
}else {
if (mid<arr.length){ //查找值的下标在arr数组额范围内，直接返回
return mid;
}else { //不在就返回right,为什么？因为后面几位的值和right的值是一样的，说明查找的值就是right
return right;
}
}
} //都找不到返回-1
return -1;
}
网友评论