在Java中,常用的查找算法有以下四种: 一、顺序查找顺序查找非常简单,就是遍历数组,找到了就返回元素下标,代码如下: public static int find(int[] arr, int targetNum){ if (arr == null) { return -1; } for (int i = 0; i < arr.length; i++) { if (arr[i] == targetNum){ return i; } } return -1; }
二、二分查找二分查找又叫折半查找,首先二分查找的数列是要有序的,如果无序就不能用二分查找。 1. 二分查找思路: - 首先确定该数组的中间下标,`mid = (left + right) / 2;
- 然后让
arr[mid] 和要和查找的元素比较,如果要查找的元素更大,说明应该向右查找,反之向左; - 将左(右)边当成一个新数组,重复第一第二步,即进行递归。找到了就结束递归,或者遍历完了数组也没找到也结束递归。
2. 代码实现: public static int find(int[] arr, int left, int right, int targetNum){ if (left > right){ return -1; } int mid = (left + right) / 2; if (arr[mid] > targetNum) { return find(arr, left, mid - 1, targetNum); } else if (arr[mid] < targetNum){ return find(arr, mid + 1, right, targetNum); } else { return mid; } }
三、插值查找插值查找也是二分查找,不同的是,mid的计算公式不再是mid = (left + right) / 2 ,变成了mid = left + (targetNum- arr[left]) / (arr[right] - arr[left]) * (right -left) ,其他的都和二分查找一样。这个mid的计算公式是大佬发明的,大家有兴趣可以用数学推导一下。 四、斐波那契查找斐波那契查找又叫黄金分割查找,黄金分割是初中学习的内容,之后又学习了斐波那契数列。 1, 1, 2, 3, 5, 8, 13……
这个就是斐波那契数列,相邻两个数的比值无限接近黄金分割值0.618。斐波那契查找就是利用斐波那契数列的这个特性来设计的查找算法。 1. 斐波那契查找介绍: 斐波那契查找和二分查找、插值查找也类似,数组也要是有序的。不同之处还是mid 的计算方法。公式为:mid = left + f(k-1) - 1 。对于这个公式做几点说明: 斐波那契数列是符合f(k) = f(k-1) + f(k-2) 的一个数列,例如1, 1, 2, 3, 5, 8…… ; 要使用斐波那契查找,就要先构建一个斐波那契数列,用来获取中间索引mid ; left 表示原始数组左边索引,初始的时候就是0,构建好斐波那契数组,我们要让f(k-1) - 1 指向数组的最后一个索引;
然后从斐波那契数组中根据mid = left + f(k-1) - 1 来获取中间索引; 然后创建一个新数组,长度为f(k) ,因为长度为f(k) 的数组才满足f(k) = f(k-1) + f(k-2) ,才能使用斐波那契数列去获取mid 索引。将原始数组的所有数拷贝过去,如果f(k) 的值大于原始数组的长度,那就就将超出长度的部分用原始数组的最后一个数填充; 根据mid 索引去上面创建的新数组中获取元素进行比较; 如果这个数比要查找的数更小,那说明在原始数组的mid 的左边,那就让right = mid - 1 ,同时k 要减1 ,因为刚才我们是在斐波那契数列f(k) 的位置获取的索引,在f(k) 的前面,有f(k-1) 个元素,将这个f(k-1) 个元素继续拆分,就可以拆成f(k-1) = f(k-2) + f(k-3) ,再根据mid = left + f(k-1-1) - 1 重新获取mid ; 如果这个数比要查找的数更大,就让left = mid + 1 ,同时k 要减2 ,因为上面说了,斐波那契数列满足f(k) = f(k-1) + f(k-2) ,在f(k) 的左边,有f(k-1) 个元素,右边有f(k-2) 个元素,继续拆分就变成了f(k-2) = f(k-3) + f(k-4) ,所以是k-2 ,再根据mid = left + f(k-1-2) - 1 重新获取mid ; 如果mid 对应是数刚好等于被查找数,那说明找到了,mid 索引就是就被查找元素的位置,但是不能直接返回mid ,因为上面说了,f(k) 可能比原始数组长度更长,超出部分用原始数组最后一个元素填充,如果直接返回mid ,此时mid 可能指向的是超出部分的元素,用这个mid 去原始数组中找,就越界了,所以应该返回mid 和right 中较小的那个。
2. 代码实现: public static int find(int[] arr, int targetNum){ int left = 0; // 原始数组最左边的下标 int right = arr.length - 1; // 原始数组最右边的下标 int k = 0; // 表示斐波那契分割数值的下标 int mid = 0; // 初始化mid为0 // 获取到斐波那契数列 int[] f = fib(arr.length); // 让f(k) - 1指向数组的最后一个索引 while (f[k] - 1 < right){ k++; } // 但是f(k)不是步长为1的递增数列,所以可能出现 f(k) - 1 的值大于原始数组最后一个索引的情况 // 比如原始数组最大索引为4,那么此时f(k)就等于5,所以需要构造一个新数组,长度不够的部分会用0填充 int[] temp = Arrays.copyOf(arr, f[k]); // 将Arrays.copyof()方法填充的0用原始数组最后一个数填充 for (int i = right + 1; i < temp.length; i++) { temp[i] = arr[right]; } // 循环查找targetNum while (left <= right){ mid = left + f[k-1] - 1; if (targetNum < temp[mid]){ // 向左查找 right = mid - 1; k--; } else if (targetNum > temp[mid]){ // 向右查找 left = mid + 1; k -= 2; } else { // 返回mid和right中较小的值 return mid <= right ? mid : right; } } return -1; }
/** * 得到一个斐波那契数列 * @return */ public static int[] fib(int length){ int[] fibArr = new int[length]; fibArr[0] = 1; fibArr[1] = 1; for (int i = 2; i < length; i++) { fibArr[i] = fibArr[i-1] + fibArr[i-2]; } return fibArr; }
|