查找算法
线性查找
- 基本思路：线性查找是最简略的查找办法，也很好了解，就是对一组有序/无序的序列进行遍历，一一比拟，直到找到对应的值
- 代码如下：
public class LinearSearch { /** * * @param arr 要查找的数组 * @param findVal 要查找的值 * @return 返回对应值的下标，如果没有返回-1 */ public static int linearSearch(int[] arr, int findVal){ if (arr == null || arr.length <= 0 ) return -1; for (int i = 0; i < arr.length; i ++){ if (arr[i] == findVal) return i; } return -1; } public static void main(String[] args) { int[] arr = {128,321,23,4,19,23,10,98,100}; int result = linearSearch(arr, 10); System.out.println(result); }}折半查找
- 介绍：折半查找也叫二分查找，要实现折半查找必须满足两个要求，第一是数列要有序的，第二是寄存数列的容器是按序寄存的
基本思路：
- 1）确定数组的两头下标mid，等于右边下标left+左边下标right的一半，mid = (left + right) / 2
2）把要找的值findVal和下标mid对应的值midVal进行比拟
- 如果findVal大于midVal，则表明要找的数在左边，向右查找，此时的left为mid + 1，right不变，从新计算mid
- 如果findVal小于midVal，则表明要找的数在右边，向左查找，此时的right为mid - 1，left不变，从新计算mid
- 如果下面两个条件都不满足，证实findVal等于midVal，则间接返回mid下标
- 3）如果说left > right，证实咱们要找的数不存在，间接返回-1
举例说明：比方有序数组{1,8,9,10,29,39,49,69}，查找39
- 如上图所示，第一次并没有找到findVall，第二次left,mid从新调整过后,找到了findVal
代码如下：
- 这里应用的是递归的形式实现折半查找
/** * 应用折半查找的前提是该数组是有序的 */public class BinarySearch { public static int binarySearch(int[] arr, int findVal){ if (arr == null || arr.length <= 0) return -1; return binarySearch(arr, 0, arr.length - 1, findVal); } public static int binarySearch(int[] arr, int left, int right, int findVal){ if (left > right) return -1; int mid = (left + right) / 2; int midVal = arr[mid]; if (findVal < midVal){ return binarySearch(arr, left, mid - 1, findVal); }else if (findVal > midVal){ return binarySearch(arr, mid + 1, right, findVal); }else { return mid; } } public static void main(String[] args) { int[] arr = {1,4,9,29,98,100,989}; int result = binarySearch(arr, 10); System.out.println(result); }}插值查找
- 介绍：插值查找是相似于折半查找，不同的中央在于mid的计算不同，折半查找是每次从取两头值，而插值查找每次从自适应mid处开始查找
基本思路：
- 与折半查找雷同，mid的计算形式不同
- mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left])
举个例子：比方有序数组{1,8,9,10,29,39,49,69}，查找39
- 如上图所示，经验了三次查找才找到了findVal
- 这里用的例子因为数组外面的整数比拟没有法则，所以通过了三次查找才找到，而折半查找只用了两次就找到了。然而如果是对于一组有法则的有序序列来说，查找的次数往往只须要一次（大家能够试一下从1-100外面去查找一个数）
代码如下：
- 这里也是采纳递归的形式实现，留神看一下上面的正文
public class InsertSearch { public static int insertSearch(int[] arr, int findVal){ if (arr == null || arr.length <= 0) return -1; return insertSearch(arr, 0, arr.length - 1, findVal); } /** ** @param arr 有序数组 * @param left 右边的下标 * @param right 左边的下标 * @param findVal 要找的值 * @return findVal对应的下标，如果找不到则返回-1 */ public static int insertSearch(int[] arr, int left, int right, int findVal){ //以下三个判断条件必须写 //第一个：当找不到的时候left会大于right //第二个和第三个：如果说要找的值不在该数组的最大值和最小值的范畴里（对于升序的数组来说） // 那么如果不加这两个条件，可能会导致最初算进去的mid不在left和right之间 if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) return -1; int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]); int midVal = arr[mid]; if (findVal > midVal){ return insertSearch(arr, mid + 1, right, findVal); }else if (findVal < midVal){ return insertSearch(arr, left, mid - 1, findVal); }else { return mid; } } public static void main(String[] args) { int[] arr = {1,8,9,10,29,39,49,69}; System.out.println(Arrays.toString(arr)); int result = insertSearch(arr, 39); System.out.println(result); }}斐波那契查找
介绍：利用斐波那契数列找到数组中的黄金分割点
- 黄金分割点：是指把一条线段宰割为两局部，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。
- 斐波那契数列中，两个相邻数的比例是有限靠近与黄金分割值0.618
- 斐波那契数列计算公式：F(k) = F(k-1) + F(k-2),F(1)=1,F(2)=2
基本思路：
- 该查找算法与折半查找相似，区别也是在于mid的计算，mid是取位于黄金分割点左近，即mid=low+F(k-1)-1
F(k-1)是什么？
- 由F(k)计算公式的性质,能够失去F(k)-1 = (F(k-1) - 1) + (F(k-2) - 1) + 1
- 也就是说，只有数组的长度为F(k)-1，就能够将该表分成长度为F(k-1) - 1 和F(k-2) - 1两段
- 而两头地位mid = low + F(k - 1) - 1
- 是否须要扩容数组：数组的长度n不肯定等于F(k)，所以须要将原来的数组长度n减少至F(k)，不肯定要齐全相等，只有比F(k)大就行，所以当n增大后就须要进行扩容
- K如何确定？ 代码如下：
while(n > F(k)) k++举个例子：比方有序数组{1,8,9,10,29,39,49,69}，查找39
- 1）首先判断是否须要扩容，n为8，k为5，F(5)=8，n刚好等于5，不须要扩容
2）第一轮，依据公式计算出mid=4，arr[mid]=29，小于39,向右查找
- left = mid + 1 = 5
- right = 7
- k = k - 2 = 3（为什么须要k-2，看上面的解释）
- mid = 6
3）第二轮，arr[mid] = arr[6] = 49，大于39，向左查找
- left = 5
- right = mid - 1 =6
- k = k - 1 =2（为什么须要k-1，看上面的解释）
- mid = 5
- 4）第三轮，arr[mid] = arr[5] = 39，等于39，找到了
k -= 2和 k --的含意：
- 如上图所示，f(k)-1能够分成两段，别离是f(k-1)-1和f(k-2)-1
- 当要找的数比arr[mid]小，咱们就把f(k)-1的长度缩减成f(k-1)-1，所以此时k--
- 当要找的数比arr[mid]大，咱们就把f(k)-1的长度缩减成f(k-2)-1，所以此时k -= 2
- 代码如下：
public class FibonacciSearch { private static int maxSize = 100; private static int count = 0; private static int[] fib(){ int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i <= maxSize - 1; i ++){ f[i] = f[i - 1] + f[i - 2]; } return f; } //斐波那契查找算法 public static int fibSearch(int[] arr, int findVal){ return fibSearch(arr, 0, arr.length - 1, findVal); } /** * * @param arr 有序数组 * @param low 数组右边的下标 * @param high 数组左边的下标 * @param findVal 要查找的值 * @return 找到的值对应的下标，如果没有返回-1 */ public static int fibSearch(int[] arr, int low, int high, int findVal){ if (arr == null || arr.length <= 0 ) return - 1; int k = 0; //示意斐波那契数列的下标 int[] f = fib(); //获取斐波那契数列 int mid = 0; //mid值 //获取斐波那契宰割数值 while (high > f[k] - 1){ k ++; } //把k与n进行比拟，如果n小就须要进行扩容 int[] temp = Arrays.copyOf(arr, f[k]); //把扩容多进去的数赋予原来arr的最初一个数据 for (int i = high + 1; i < temp.length; i ++){ temp[i] = arr[high]; } System.out.println("查找之前的工作："); System.out.println("t扩容后的数组arr：" + Arrays.toString(temp)); System.out.println("tleft：" + low); System.out.println("tright：" + high); System.out.println("tk：" + k); //应用while循环，找到咱们的数Key while (low <= high){ //设置两头点 mid = low + f[k-1] - 1; System.out.println("这是第" + ++count +"轮："); System.out.println("tleft：" + low); System.out.println("tright：" + high); System.out.println("tk：" + k); System.out.println("tf[k-1]-1：" + (f[k-1] -1)); System.out.println("tmid：" + mid); if (findVal < temp[mid]){ high = mid - 1; //这里为什么是k -- //1、全副元素 = 后面的元素 + 后边的元素 //2、f(k) = f(k-1) + f(k-2) //3、后面有f(k-1)个元素，所以能够持续拆分，f(k-1) = f(k-2)+f(k-3) k --; }else if (findVal > temp[mid]){ low = mid + 1; //为什么是k -= 2 //1、全副元素 = 后面的元素 + 前面的元素 //2、f(k) = f(k-1) + f(k-2) //3、因为咱们有f[k-2]，所以能够持续拆分f[k-2]=f[k-3]+f[k-4] //4、即在f[k-2]的后面进行查找 //5、下次循环mid = f[k - 1 - 2] - 1 k -= 2; }else { if (mid <= high){ return mid; }else { return high; } } } return -1; } public static void main(String[] args) { int[] arr = {1,8,9,10,29,39,49,69}; int resultIndex = fibSearch(arr, 39); System.out.println(resultIndex); }}