常用查找算法
1.顺序（线性）查找
逐一进行比对查找
2.二分查找/折半查找
2.1代码
（1）使用递归
1 package ChaZhao; 2 /* 3 * 二分法查找：前提是数组为有序数组 4 * 没有重复数字 5 * 使用递归 6 */ 7 public class ErFenSearch { 8 9 public static void main(String[] args){ 10 int[] a={2,6,8,9,18,28,29,68}; 11 SearchQ(a,0,a.length-1,68); 12 } 13 14 public static void SearchQ(int[]a,int left,int right,int q){ 15 int mid=(left+right)/2; 16 if(left==right){ 17 if(a[left]==q){ 18 System.out.println("已找到"+q+"下标为:"+left); 19 }else{ 20 System.out.println("查无此数!!!"); 21 } 22 return; 23 }else{ 24 if(q==a[mid]){ 25 System.out.println("已找到"+q+"下标为:"+mid); 26 return; 27 } 28 if(q<a[mid]){ 29 SearchQ(a,left,mid-1,q); 30 } 31 if(q>a[mid]){ 32 SearchQ(a,mid+1,right,q); 33 } 34 } 35 36 } 37 38 }
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码优化：
1 package ChaZhao; 2 /* 3 * 二分法，没重复数字 4 * 使用递归 5 * 代码优化 6 */ 7 public class ErFenSearchDemo2 { 8 public static void main(String[] args){ 9 int[] a={2,6,8,9,18,28,29,68,100}; 10 int index=SearchQ(a,0,a.length-1,100); 11 if(index<0){ 12 System.out.println("查无此数!!!"); 13 }else{ 14 System.out.println("已查到，下标为"+index); 15 } 16 } 17 18 public static int SearchQ(int[]a,int left,int right,int q){ 19 if(left>right){ 20 return -1; 21 } 22 int mid=(left+right)/2; 23 if(q>a[mid]){ 24 return SearchQ(a,mid+1,right,q); 25 }else if(q<a[mid]){ 26 return SearchQ(a,left,mid-1,q); 27 }else{ 28 return mid; 29 } 30 } 31 32 }
（2）不使用递归
1 package ChaZhao; 2 /* 3 * 二分法查找:：前提是数组为有序数组 4 * 没有重复数字 5 * 不使用递归 6 */ 7 public class ErFenSearchDemo { 8 public static void main(String[] args){ 9 int[] a={2,6,8,9,18,28,29,68,100}; 10 int index=SearchQ(a,0,a.length-1,99); 11 if(index<0){ 12 System.out.println("查无此数!!!"); 13 }else{ 14 System.out.println("已查到，下标为"+index); 15 } 16 } 17 18 public static int SearchQ(int[]a,int left,int right,int q){ 19 20 while(left<=right){ 21 int mid=(left+right)/2; 22 if(q==a[mid]){ 23 return mid; 24 }else{ 25 if(q<a[mid]){ 26 right=mid-1; 27 }else{ 28 left=mid+1; 29 } 30 } 31 } 32 return -1; 33 34 35 } 36 37 }
2.2 算法优化：当数组中有重复数字时
（1）使用递归
1 package ChaZhao; 2 /* 3 * 二分法查找：前提是数组为有序数组 4 * 有重复数字 5 * 使用递归 6 */ 7 public class ErFenSearchDemo4 { 8 9 public static void main(String[] args){ 10 int[] a={2,6,8,9,28,28,28,28,29,68,99}; 11 SearchQ(a,0,a.length-1,28); 12 } 13 14 public static void SearchQ(int[]a,int left,int right,int q){ 15 int mid=(left+right)/2; 16 if(left==right){ 17 if(a[left]==q){ 18 System.out.println("已找到"+q+"下标为:"+left); 19 }else{ 20 System.out.println("查无此数!!!"); 21 } 22 return; 23 }else{ 24 if(q==a[mid]){ 25 26 //向mid左边遍历查找 27 int index=mid; 28 while(q==a[index]&&index>=left){ 29 System.out.println("已找到"+q+"下标为:"+index); 30 index--; 31 } 32 33 34 //向mid右边遍历查找 35 int temp=mid+1; 36 while(q==a[temp]&&temp<=right){ 37 System.out.println("已找到"+q+"下标为:"+temp); 38 temp++; 39 } 40 41 42 return; 43 } 44 if(q<a[mid]){ 45 SearchQ(a,left,mid-1,q); 46 } 47 if(q>a[mid]){ 48 SearchQ(a,mid+1,right,q); 49 } 50 } 51 52 } 53 54 }
3.插值查找算法
插值查找是利用插值公式来计算猜测搜索键值的位置。搜索方式与二分搜索相同，只不过二分法将中间的位置设想为需要查找的数的位置，而插值查找是用插值公式计算键值位置，将这个计算出来的位置，设想为需要查找的数的位置
公式：mid =left+ ((q - a[left])/(a[right]- a[left]))*(right-left);
所以说，插值查找和二分法唯一的不同就是mid的取值，二分法取得是数组的中间，而插值法是通过运算取得的值，除此之外，二分法和插值法没有什么不同
3.1使用条件
数组有序排列，且分布均匀，若是分布不均，则效率与二分法查找不相上下
3.2 代码实现
1 package ChaZhao; 2 /* 3 * 使用插值法查找 4 */ 5 public class ChaZhiSearchDemo { 6 public static void main(String[] args){ 7 int[] a={2,6,8,9,18,28,29,68,100}; 8 int index=SearchQ(a,0,a.length-1,18); 9 if(index<0){ 10 System.out.println("查无此数!!!"); 11 }else{ 12 System.out.println("已查到，下标为"+index); 13 } 14 } 15 public static int SearchQ(int[]a,int left,int right,int q){ 16 if(left<=right){ 17 int mid=left+((q-a[left])/(a[right]-a[left]))*(right-left); 18 if(q<a[mid]){ 19 return SearchQ(a,left,mid-1,q); 20 }else if(q>a[mid]){ 21 return SearchQ(a,mid+1,right,q); 22 }else{ 23 return mid; 24 } 25 }else{ 26 return -1; 27 } 28 } 29 30 }
4.斐波那契查找算法（黄金分割查找算法）
斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。斐波那契思想与二分法相类似，不过中间点不再是中点，而变成了黄金分割点的附近
4.1 基本思想
在斐波那契数列找一个等于或第一个大于查找表中元素个数的数 F[n]，然后将原查找表的长度扩展为 Fn (如果要补充元素，则重复补充原查找表最后一个元素，直到原查找表中满足 F[n] 个元素)；扩展完成后进行斐波那契分割，即 F[n] 个元素分割为前半部分 F[n-1] 个元素，后半部分 F[n-2] 个元素；接着找出要查找的元素在哪一部分并递归，直到找到。
公式：mid=left+F(k-1)-1
4.2 步骤
（1）构建斐波那契数列；
（2）找出查找表长度对应的斐波那契数列中的元素 F(n)；
（3）如果查找表长度小于斐波那契数列中对应的元素 F(n) 的值，则补充查找表（以查找表最后一个元素补充）；
（4）根据斐波那契数列特点对查找表进行区间分隔，确定查找点 mid = left+F(n-1)-1（减 1 是因为数组下标从 0 开始）；
（5）判断中间值 arr[mid] 和目标值的关系，确定下一步策略：
a. 如果目标值小于中间值，说明目标值在左区间。由于左区间长度为 F(n-1)，因此 n 应该更新为 n-1，然后再次执行 4、5 两步；
b. 如果目标值大于中间值，说明目标值在右区间。由于右区间长度为 F(n-2)，因此 n 应该更新为 n-2，然后再次执行 4、5 两步；
c. 如果目标值等于中间值，说明找到了目标值。但此时还需判别该目标值是原查找表中的元素还是填充元素：
|. 如果是原查找表中的元素，直接返回索引；
||. 如果是填充元素，则返回原查找表的最后一个元素的索引，即 arr.length-1。（因为扩展数组是以原查找表最后一个元素来填充，如果目标值 是填充元素，则说明原查找表最后一个元素值就是目标值）
4.3代码
1 package ChaZhao; 2 3 import java.util.Arrays; 4 5 /* 6 * 斐波那契插值算法 7 * 不用递归 8 */ 9 10 public class FeiBoNaQieSearch { 11 public static void main(String[] args){ 12 int[]a={2,6,8,9,18,28,29,68,100}; 13 int index=FeiBoSearchQ(a,18); 14 if(index<0){ 15 System.out.println("查无此数!!!"); 16 }else{ 17 System.out.println("已查到，下标为"+index); 18 } 19 } 20 21 22 //获取斐波那契数列 23 public static int[] getF(){ 24 int maxSize=20; 25 int[]f=new int[maxSize]; 26 f[0]=1; 27 f[1]=1; 28 for(int i=2;i<maxSize;i++){ 29 f[i]=f[i-1]+f[i-2]; 30 } 31 return f; 32 } 33 34 public static int FeiBoSearchQ(int[]a,int q){ 35 int left=0; 36 int right=a.length-1; 37 int k=0; 38 int[]f=getF(); 39 40 //找到获取的斐波那契数列中的第一个值等于或大于right的元素是斐波那契数列中第几个数 41 /* 42 * f[k]-1>=right 43 */ 44 while(right>f[k]-1){//因为数组的下标从0开始，所以这里是f[k-1] 45 k++; 46 } 47 48 49 //临时创建一个数组temp，用来将a拷贝到其中，因为数组长度为f[k]，而f[k]>=a.length,，其余位置补0 50 int[]temp=Arrays.copyOf(a, f[k]); 51 52 //将上一步多出来的补了0的位置的数换成a数组的最后一个元素 53 for(int i=a.length;i<temp.length;i++){ 54 temp[i]=a[a.length-1]; 55 } 56 57 //从temp[]中查询 58 while(left<=right){ 59 int mid=left+f[k-1]-1; 60 if(q<temp[mid]){ 61 right=mid-1; 62 k--; 63 }else if(q>temp[mid]){ 64 left=mid+1; 65 k-=2; 66 }else{ 67 68 //找到存在两种可能：一是找到的是原查找表中的元素，二是找到的是填充值。因此需要判别 69 if(mid<=right) 70 { 71 return mid; 72 } 73 else 74 { 75 return right; 76 } 77 } 78 } 79 return -1; 80 } 81 82 }
联系客服
