1.查找算法介绍
1.1 在java中常用的查找:顺序(线性)查找,二分查找/折半查找,插值查找,斐波那契查找
2.线性查找源代码
1 package cn.atguigu.Search; 2 3 public class SeqSearch { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 int arr[]= {1,9,11,-1,34,89};//没有顺序的数组 8 int index=seqSearch(arr, 11); 9 if(index==-1) { 10 System.out.println("没有找到"); 11 }else { 12 System.out.println("找到,下表为="+index); 13 } 14 } 15 /** 16 * 实现的线性查找是找到一个满足条件的值就返回 17 * @param arr 18 * @param value 19 * @return 20 */ 21 public static int seqSearch(int[] arr, int value) { 22 //线性查找就是逐一对比,发现有相同值,就返回下标 23 for(int i=0;i<arr.length;i++) { 24 if(arr[i]==value) { 25 return i; 26 } 27 } 28 return -1; 29 } 30 }
3. 二分查找
3.2二分查找需要是有序列的
3.3 思路:
step1:首先确定该数组的中间的下标mid=(left+right)/2
step2:然后让需要查找的数findVal和arr[mid]比较,
step2.1:findVal>arr[mid],说明要查找的数在mid的右边,因此需要递归的向右查找
step2.2: findVal<arr[mid],说明要查找的数在mid的左边,因此需要递归的向左查找
step2.3:findVal==arr[mid],说明找到就返回
结束递归的条件:
(1)找到结果
(2)递归完整个数组,仍然没找到findVal,也需要结束递归,当left>right就需要退出
3.4 源代码:
1 package cn.atguigu.Search; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 //注意:使用二分查找的前提是 该数组是有序的 7 public class BinarySearch { 8 9 public static void main(String[] args) { 10 // TODO Auto-generated method stub 11 int arr[]= {1,8,10,89,1000,1234}; 12 /* 13 * int index=binarySearch(arr, 0, arr.length-1, 1000); if(index==-1) { 14 * System.out.println("没找到"); }else { System.out.println(index); } 15 */ 16 List<Integer> resIndexList=binarySearchmore(arr, 0, arr.length-1, 1100); 17 System.out.println("resIndexList="+resIndexList); 18 19 } 20 //二分查找方法 21 /** 22 * 23 * @param arr 数组 24 * @param left 左边的索引 25 * @param right 右边的索引 26 * @param findVal 要查找的值 27 * @return 如果找到就返回下标,如果没有找到,就返回-1 28 */ 29 public static int binarySearch(int[] arr,int left,int right,int findVal) { 30 int mid=(left+right)/2;//找到中间的下标 31 int midVal=arr[mid]; 32 if(left>right) { 33 return -1; 34 } 35 if(findVal>midVal) {//如果待查找的值大于中间值,说明需要向右递归 36 return binarySearch(arr, mid+1, right, findVal); 37 }else if(findVal<midVal) {//否则向左递归 38 return binarySearch(arr, left, mid-1, findVal); 39 }else { 40 return mid; 41 } 42 } 43 44 //实现找到数组中重复的数字 45 /* 46 * 思路分析 47 * 1.在找到mid 索引值,不要马上返回 48 * 2.向mid索引值的左边扫描,将所有满足条件的下标,添加到ArrayList 49 * 3.向mid索引值的右边扫描,将所有满足条件的下标,添加到ArrayList 50 * 4.将ArrayList返回 51 */ 52 public static ArrayList<Integer> binarySearchmore(int[] arr,int left,int right,int findVal) { 53 int mid=(left+right)/2;//找到中间的下标 54 int midVal=arr[mid]; 55 if(left>right) { 56 return new ArrayList<Integer>(); 57 } 58 if(findVal>midVal) {//如果待查找的值大于中间值,说明需要向右递归 59 return binarySearchmore(arr, mid+1, right, findVal); 60 }else if(findVal<midVal) {//否则向左递归 61 return binarySearchmore(arr, left, mid-1, findVal); 62 }else { 63 ArrayList<Integer> list=new ArrayList<Integer>(); 64 //先向左边扫描 65 int temp=mid-1; 66 while(true) { 67 if(temp<0||arr[temp]!=findVal) {//退出 68 break; 69 }//否则,就将temp放入到集合中 70 list.add(temp); 71 temp--;//temp左移 72 } 73 list.add(mid);//放入中间
temp=mid+1; 74 //再向右边扫描 75 while(true) { 76 if(temp>arr.length-1||arr[temp]!=findVal) {//退出 77 break; 78 }//否则,就将temp放入到集合中 79 list.add(temp); 80 temp++;//temp右移 81 } 82 return list; 83 } 84 } 85 }
4.插值查找
4.1 插值查找算法类似于二分查找,不同的是查找值每次都从自适应mid处开始查找
mid=(low+high)/2=low+0.5*(high-low)===>mid=low+(key-a[low])*(high-low)/(a[high)-a[low])
key指的是待查找的值
4.2 插值查找算法也要求数组是有序的
对于数据量比较大,关键字分布比较均匀的查找表来说,采用插值查找,速度比较快
关键字分布不均匀的情况下,该方法不一定比折半查找要好
4.3 源代码
1 package cn.atguigu.Search; 2 3 import java.util.ArrayList; 4 5 public class InsertValueSearch { 6 7 public static void main(String[] args) { 8 // TODO Auto-generated method stub 9 int[] arr= new int[100]; 10 for (int i = 0; i < arr.length; i++) { 11 arr[i]=i+1; 12 } 13 arr[23]=23; 14 arr[24]=23; 15 ArrayList<Integer> list=insertValueSearch(arr, 0, arr.length-1, 23); 16 System.out.println(list); 17 18 } 19 //插值查找算法,查找多个值 20 public static ArrayList<Integer> insertValueSearch(int[] arr,int left,int right,int key) { 21 int mid=left+(key-arr[left])*(right-left)/(arr[right]-arr[left]);//设定中间值 22 if(left>right||key<arr[0]||key>arr[arr.length-1]) {//如果左边大于右边,或者当其小于最小值,大于最大值时,则没有找到 23 return new ArrayList<Integer>(); 24 } 25 if(key<arr[mid]) {//如果这个值小于中间值,向左边查找 26 return insertValueSearch(arr, left, mid-1, key); 27 }else if(key>arr[mid]) {//如果这个值大于中间值,向右边查找 28 return insertValueSearch(arr, mid+1, right, key); 29 }else {//如果相等 30 ArrayList<Integer> list=new ArrayList<Integer>(); 31 int temp=mid-1; 32 while(true) {//向mid的左边查找 33 if(temp<0||arr[temp]!=key) { 34 break; 35 } 36 list.add(temp); 37 temp--; 38 } 39 list.add(mid); 40 temp=mid+1; 41 while(true) {//向mid的右边查找 42 if(temp>arr.length-1||arr[temp]!=key) { 43 break; 44 } 45 list.add(temp); 46 temp++; 47 } 48 49 return list; 50 } 51 } 52 53 }
5.斐波那契(黄金分割法)查找
5.1 斐波那契查找原理与前两种相似,仅仅改变中间结点的位置,mid位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列表)
由斐波那契数列F(k)=F(k-1)+F(k-2)的性质,可以得到(F(k)-1)=(F(k-1)-1)+(F(k-2)-1)+1,该式说明顺序表的长度为F(k)-1,可以将该表分成长度为F(k-1)-1和F(k-2)-1;类似的,每一字段也可以用相同的方式分割;但顺序表长度n不一定正好等于F(k)-1,所以需要将原来的顺序表长度n增加至F(k)-1。这里的k值只要能使得F(k)-1恰好大于或等于n即可,由一下代码得到,顺序表长度增加后,新增的位置(从n+1到F(k)-1位置),都赋n位置的值即可。
while(n>fib(k)-1){ k++; }
5.2 斐波那契查找仍然要求是有序数组
5.3 源代码
1 package cn.atguigu.Search; 2 import java.util.Arrays; 3 4 public class FibonacciSearch { 5 public static int maxSize=20; 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 int[] arr= {1,8,10,89,1000,1234}; 9 int index=fibonacciSearch(arr, 1234); 10 System.out.println(index); 11 } 12 //编写斐波那契查找算法 13 //使用非递归方式编写算法 14 public static int fibonacciSearch(int[] arr,int key) { 15 int low=0; 16 int high=arr.length-1; 17 int k=0;//表示斐波那契分割数值的下标 18 int mid=0;//存放mid值 19 int f[]=fib(); 20 //获取到斐波那契分割数列的下标 21 while(high>f[k]-1) { 22 k++; 23 } 24 //因为f[k] 可能大于 a 的长度,因此需要使用Arrays类,构造一个新的数组,并指向a 25 //不足的部分会使用0填充 26 int[] temp=Arrays.copyOf(arr, f[k]); 27 //对新的数组n到f[k]-1位置的数据用arr[high]填充 28 for(int i=high+1;i<temp.length;i++) { 29 temp[i]=arr[high]; 30 } 31 //使用while循环来处理,找到key 32 while(low<=high) {//只要这个条件满足,就可以一直找 33 mid=low+f[k-1]-1; 34 if(temp[mid]>key) {//若该数小于mid指向的数,向数组前部查找 35 high=mid-1; 36 k--;//因为f[k]=f[k-1]+f[k-2],因为前面有f[k-1]个元素,所以可以继续拆分f[k-1]=f[k-2]+f[k-3],即在f[k-1]的前部继续查找,即mid=f[k-1-1]-1 37 }else if(temp[mid]<key){//若该数大于mid指向的数,向数组后部查找 38 low=mid+1; 39 k-=2;//在f[k-2]的后部继续查找,即f[k-1]=f[k-3]+f[k-4],mid=f[k-1-2]-1; 40 }else {//找到 41 //需要确定,返回的是哪个下标 42 // return mid; 43 if (mid <= high) { 44 return mid; 45 } else { 46 return high; 47 } 48 } 49 } 50 return -1; 51 } 52 //因为后面我们mid=low+f(k-1)-1,需要使用到斐波那契数列,因此需要先获取到 53 //使用非递归方式得到一个斐波那契数列 54 public static int[] fib() { 55 int[] f=new int[maxSize]; 56 f[0]=1; 57 f[1]=1; 58 for(int i=2;i<maxSize;i++) { 59 f[i]=f[i-1]+f[i-2]; 60 } 61 return f; 62 } 63 }