场景
Java中对数据需要进行查找,归纳整理常用查找算法及示例。
注:
博客:
https://blog.csdn.net/badao_liumang_qizhi
实现
1、顺序查找
顺序查找法就是将数据一项一项地按照顺序逐个查找,所以不管数据顺序如何,
都得从头到位遍历一遍。该方法的优点就是文件在查找前不需要进行任何处理与排序,
缺点就是查找速度较慢。
示例代码:
public class ShunXv { public static void main(String args[]) throws IOException { String strM; BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in)); int data[] =new int[100]; int i,j,find,val=0; for (i=0;i<80;i++) data[i]=(((int)(Math.random()*150))%150+1); while (val!=-1) { find=0; System.out.print("请输入要查找的键值(1~150),输入-1则退出程序:"); strM=keyin.readLine(); val=Integer.parseInt(strM); for (i=0;i<80;i++) { if(data[i]==val) { System.out.print("在第"+(i+1)+"个位置找到键值 ["+data[i]+"]\n"); find++; } } if(find==0 && val !=-1) System.out.print("######没有找到 ["+val+"]######\n"); } System.out.print("数据内容:\n"); for(i=0;i<10;i++) { for(j=0;j<8;j++) System.out.print(i*8+j+1+"["+data[i*8+j]+"] "); System.out.print("\n"); } } }
2、二分查找法
如果要查找的数据已经实现排好序了,就可以使用二分查找法来进行查找。二分查找就是将数据分割成两份,
再比较键值与中间值的大小。如果键值小于中间值,就可以确定要查找的数据再前半部分,否则在后半部分,
如此分割数次直到找到或确定不存在为止。
示例代码:
public class ErFen { public static void main(String args[]) throws IOException { int i,j,val=1,num; int data[] =new int[50]; String strM; BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in)); for (i=0;i<50;i++) { data[i]=val; val+=((int)(Math.random()*100)%5+1); } while (true) { num=0; System.out.print("请输入查找键值(1-150),输入-1结束:"); strM=keyin.readLine(); val=Integer.parseInt(strM); if(val==-1) break; num=bin_search(data,val); if(num==-1) System.out.print("##### 没有找到["+val+"] #####\n"); else System.out.print("在第 "+(num+1)+"个位置找到 ["+data[num]+"]\n"); } System.out.print("数据内容:\n"); for(i=0;i<5;i++) { for(j=0;j<10;j++) System.out.print((i*10+j+1)+"-"+data[i*10+j]+" "); System.out.print("\n"); } System.out.print("\n"); } public static int bin_search(int data[],int val) { int low,mid,high; low=0; high=49; System.out.print("正在查找......\n"); while(low <= high && val !=-1) { mid=(low+high)/2; if(val<data[mid]) { System.out.print(val+" 介于位置 "+(low+1)+"["+data[low]+"]及中间值 "+(mid+1)+"["+data[mid]+"],找左半边\n"); high=mid-1; } else if(val>data[mid]) { System.out.print(val+" 介于中间值位置 "+(mid+1)+"["+data[mid]+"]及 "+(high+1)+"["+data[high]+"],找右半边\n"); low=mid+1; } else return mid; } return -1; } }
3、差值查找法
差值查找法是二分法的改进版,按照数据位置的分布,利用公式预测数据所在的位置,再以二分法的方式渐渐逼近。
差值查找法的公式为:mid = low +((key - data[low]) / (data[high] - data[low])) *(high - low)
其中key是要查找的键值,data[high]、data[low]是剩余待查找记录中的最大最小值。
一般而言,差值查找法优先于顺序查找法,数据的分布越平均,查找速度越快。
示例代码:
public class ChaZhi { public static void main(String args[]) throws IOException { int i,j,val=1,num; int data[]=new int[50]; String strM; BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in)); for (i=0;i<50;i++) { data[i]=val; val+=((int)(Math.random()*100)%5+1); } while(true) { num=0; System.out.print("请输入查找键值(1-"+data[49]+"),输入-1结束:"); strM=keyin.readLine(); val=Integer.parseInt(strM); if(val==-1) break; num=interpolation(data,val); if(num==-1) System.out.print("##### 没有找到["+val+"] #####\n"); else System.out.print("在第 "+(num+1)+"个位置找到 ["+data[num]+"]\n"); } System.out.print("数据内容:\n"); for(i=0;i<5;i++) { for(j=0;j<10;j++) System.out.print((i*10+j+1)+"-"+data[i*10+j]+" "); System.out.print("\n"); } } public static int interpolation(int data[],int val) { int low,mid,high; low=0; high=49; int tmp; System.out.print("正在查找......\n"); while(low<= high && val !=-1 ) { tmp=(int)((float)(val-data[low])*(high-low)/(data[high]-data[low])); mid=low+tmp; //插值查找法公式 if (mid>50 || mid<-1) return -1; if (val<data[low] && val<data[high]) return -1; else if (val>data[low] && val>data[high]) return-1; if (val==data[mid]) return mid; else if (val < data[mid]) { System.out.print(val+" 介于位置 "+(low+1)+"["+data[low]+"]及中间值 "+(mid+1)+"["+data[mid]+"],找左半边\n"); high=mid-1; } else if(val > data[mid]) { System.out.print(val+" 介于中间值位置 "+(mid+1)+"["+data[mid]+"]及 "+(high+1)+"["+data[high]+"],找右半边\n"); low=mid+1; } } return -1; } }
4、斐波那契查找
斐波那契查找要求有序,采用和二分查找/插值查找相似的区间分割策略,仅仅是改变了开始找点的位置,
mid不再是中间或插值得到,而是位于黄金分割点附近,即mid = low+F(k-1)-1。
黄金比例:整体与较大部分的比值为1:0.618 。斐波那契数(黄金分割数列:1,1,2,3,5,8,13,21...)随着此数列的递增,
前后两个数的比例会越来越接近0.618
示例代码:
public class FeiBoNaQi { public static void main(String[] args) { //待查找序列 int[] arr = {1,3,5,6,8,13,45,67,133}; int i = fiboSearch(arr, 133); System.out.println("斐波那契查找目标值133在数组中的下标为: "+i); } //得到一个斐波那契数组 public static int[] fibonacci(int n) { //初始化数组 int[] fibo = new int[n]; if (n >= 1) fibo[0] = 1; if (n >= 2) fibo[1] = 1; for (int i = 2; i < n; i++) { fibo[i] = fibo[i - 1] + fibo[i - 2]; } return fibo; } //主方法 /** * @param arr 待查找序列 * @param findVal 查找的目标值 * @return 返回目标值所在的下标 */ public static int fiboSearch(int[] arr, int findVal) { int low = 0; int high = arr.length - 1; int k = 0; int mid = 0; int maxsize = 20; //得到斐波那契数组 int[] fibo = fibonacci(maxsize); //判断待查找序列长度应该为哪一个斐波那契数 while (high > fibo[k] - 1) { k++; } //填充待排序列, 长度为f[k]-1 //把老数组复制到长度为 f[k]的新数组中 //超出老数组长度的用0填充 int[] temp = Arrays.copyOf(arr, fibo[k]-1); //填充temp数组中为0的部分 for (int i = high + 1; i < temp.length; i++) { temp[i] = arr[high]; } System.out.println("填充了最后元素的临时数组: "+Arrays.toString(temp)); //正式开始查找 while (low <= high) { mid = low + fibo[k - 1] - 1; //不断比较不同区间内 findVal 与 temp[mid]的关系 if( findVal < temp[mid]){ high = mid -1; k -= 1; }else if( findVal > temp[mid]){ low = mid+1; k -= 2; }else{ //需要确定返回的是那个下标 if(mid <= high){ return mid; }else{ return high; } } } return -1; } }