尚硅谷图解Java数据结构和算法.pdf

1、线性查找

线性查找是一种非常简单的查找方式。查找思路是：从数组的一个元素出发，一个个地和要查找的值进行比较，如果发现有相同的元素就返回该元素的下标。反之返回-1（未找到）

  1. public class Demo1 {
  2.    public static void main(String[] args) {
  3.       int[] arr = {1, 11, -1, 0, 55};
  4.       int result = seqSearch(arr, 1);
  5.       if(result == -1) {
  6.          System.out.println("数组中没有该元素");
  7.       }else {
  8.          System.out.println("该元素在数组的下标是：" + result);
  9.       }
  10.    }
  12.    /**
  13.     * 线性查找
  14.     * @param arr 查找的数组
  15.     * @param num 待查找的数字
  16.     * @return 数字的索引
  17.     */
  18.    public static int seqSearch(int[] arr, int num) {
  19.       for(int i = 0; i<arr.length; i++) {
  20.          if(arr[i] == num) {
  21.             return i;
  22.          }
  23.       }
  24.       return -1;
  25.    }
  26. }

2、二分查找

进行二分查找的数组必须为有序数组

  • 设置一个指向中间元素下标的变量mid，mid=(left + right)/2
  • 让要查找的元素和数组mid下标的元素进行比较
    • 如果查找的元素大于arr[mid]，则left变为mid后面一个元素的下标
    • 如果查找的元素小于arr[mid]，则right变为mid前一个元素的下标
    • 如果查找的元素等于arr[mid]，则mid就是要查找元素所在的位置
  • 当left > rigth时，说明元素不在该数组中

image.png
image.png

  1. //注意：使用二分查找的前提是 该数组是有序的.
  2. public class BinarySearch {
  3.     public static void main(String[] args) {
  4.         int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
  5.         int result = binarySearch(arr,0, arr.length - 1,10000);
  6.         if(result == -1){
  7.             System.out.println("数组中没有该元素");
  8.         }else {
  9.             System.out.println("该元素在数组的下标是：" + result);
  10.         }
  11.     }
  13.     /**
  14.      * 二分查找算法
  15.      * @param arr 数组
  16.      * @param left 左边的索引
  17.      * @param right 右边的索引
  18.      * @param findVal  要查找的值
  19.      * @return 如果找到就返回下标，如果没有找到，就返回 -1
  20.      */
  21.     public static int binarySearch(int[] arr,int left,int right,int findVal){
  22.         // 当 left > right 时，说明递归整个数组，但是没有找到
  23.         if (left >right){
  24.             return -1;
  25.         }
  26.         int mid = (left + right) / 2;
  27.         int midVal = arr[mid];
  29.         if (findVal > midVal){//向右递归
  30.             return binarySearch(arr,mid + 1,right,findVal);
  31.         }else if (findVal < midVal){//向左递归
  32.             return binarySearch(arr, left, mid - 1, findVal);
  33.         }else {
  34.             return mid;
  35.         }
  36.     }
  37. }

但是有可能要查找的元素有多个。这时就需要在找到一个元素后，不要立即返回，而是扫描其左边和右边的元素，将所有相同元素的下标保存到一个数组中，然后一起返回

  1. //注意：使用二分查找的前提是 该数组是有序的.
  2. public class BinarySearch {
  3.     public static void main(String[] args) {
  4.         int arr[] = { 1, 8,10, 89,1000,1000, 1234 };
  5.         List<Integer> reslist = binarySearch2(arr,0, arr.length - 1,1000);
  6.         if (reslist.size() == 0){
  7.             System.out.println("数组中没有该元素");
  8.         }else {
  9.             System.out.println("该元素在数组的下标是：" + reslist);
  10.         }
  11.     }
  12.     //完成一个课后思考题:
  13.     /*
  14.      * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
  15.      * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
  16.      *
  17.      * 思路分析
  18.      * 1. 在找到mid 索引值，不要马上返回
  19.      * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  20.      * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  21.      * 4. 将Arraylist返回
  22.      */
  23.     public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
  24.         // 当 left > right 时，说明递归整个数组，但是没有找到
  25.         if (left >right){
  26.             return new ArrayList<Integer>();
  27.         }
  28.         int mid = (left + right) / 2;
  29.         int midVal = arr[mid];
  31.         if (findVal > midVal){//向右递归
  32.             return binarySearch2(arr,mid + 1,right,findVal);
  33.         }else if (findVal < midVal){//向左递归
  34.             return binarySearch2(arr, left, mid - 1, findVal);
  35.         }else {
  36.             List<Integer> resultIndexList = new ArrayList<>();
  37.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  38.             int temp = mid -1;
  39.             while (true){
  40.                 if (temp < 0 || arr[temp] != findVal) {
  41.                     break;
  42.                 }
  43.                     //否则，就temp 放入到 resIndexlist
  44.                     resultIndexList.add(temp);
  45.                     temp--;
  46.             }
  47.             resultIndexList.add(mid);
  49.             //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  50.             temp = mid + 1;
  51.             while (true){
  52.                 if (temp > arr.length - 1 || arr[temp] != findVal) {
  53.                     break;
  54.                 }
  55.                     resultIndexList.add(temp);
  56.                     temp++;
  57.             }
  58.             return resultIndexList;
  59.         }
  60.     }
  61. }

3、插值查找

在二分查找中，如果我们 要找的元素位于数组的最前端或者最后段，这时的查找效率是很低的。所以在二分查找至上，引入了插值查找，也是一种基于有序数组的查找方式
插值查找与二分查找的区别是：插值查找使用了一种自适应算法，用这种算法来计算mid。
mid的值在两种查找算法中的求法：

  • 二分查找：mid = (left + right)/2
  • 插值查找：mid = left + (right - left) * (num - arr[left]) / (arr[right] - arr[left])
    • 其中num为要查找的那个值

image.png

  1. public class InsertValueSearch {
  2.     public static void main(String[] args) {
  3.         int[] arr = new int[100];
  4.         for (int i = 0; i < 100; i++) {
  5.             arr[i] = i;
  6.         }
  7.         //int arr[] = { 1, 8,10, 89,1000,1000, 1234 };
  8.         List<Integer>  resListBinary = binarySearch2(arr,0, arr.length - 1,66 );
  9.         List<Integer> reslistInsert = insertValueSearch(arr,0, arr.length - 1,66);
  10.         if (resListBinary.size() == 0){
  11.             System.out.println("数组中没有该元素");
  12.         }else {
  13.             System.out.println("二分查找：该元素在数组的下标是：" + resListBinary);
  14.         }
  15.         System.out.println("*************************");
  16.         if (reslistInsert.size() == 0){
  17.             System.out.println("数组中没有该元素");
  18.         }else {
  19.             System.out.println("插值查找：该元素在数组的下标是：" + reslistInsert);
  20.         }
  22.     }
  23.     //编写插值查找算法
  24.     //说明：插值查找算法，也要求数组是有序的
  25.     /**
  26.      *插值查找
  27.      * @param arr 数组
  28.      * @param left 左边索引
  29.      * @param right 右边索引
  30.      * @param findVal 查找值
  31.      * @return 如果找到，就返回对应的下标，如果没有找到，返回-1
  32.      */
  33.     public static List<Integer> insertValueSearch(int[] arr,int left,int right,int findVal){
  34.         System.out.println("插值查找次数~~");
  35.         //注意：findVal < arr[0]  和  findVal > arr[arr.length - 1] 必须需要
  36.         //否则我们得到的 mid 可能越界
  37.         if(left > right || findVal < arr[0] || findVal > arr[arr.length - 1]){
  38.             return new ArrayList<Integer>();
  39.         }
  40.         int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
  41.         int midVal = arr[mid];
  43.         if (findVal > midVal){//向右递归
  44.             return insertValueSearch(arr,mid + 1,right,findVal);
  45.         }else if (findVal < midVal){//向左递归
  46.             return insertValueSearch(arr, left, mid - 1, findVal);
  47.         }else {
  48.             List<Integer> resultIndexList = new ArrayList<>();
  49.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  50.             int temp = mid -1;
  51.             while (true){
  52.                 if (temp < 0 || arr[temp] != findVal) {
  53.                     break;
  54.                 }
  55.                 //否则，就temp 放入到 resIndexlist
  56.                 resultIndexList.add(temp);
  57.                 temp--;
  58.             }
  59.             resultIndexList.add(mid);
  61.             //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  62.             temp = mid + 1;
  63.             while (true){
  64.                 if (temp > arr.length - 1 || arr[temp] != findVal) {
  65.                     break;
  66.                 }
  67.                 resultIndexList.add(temp);
  68.                 temp++;
  69.             }
  70.             return resultIndexList;
  71.         }
  72.     }
  74.     //二分查找
  75.     public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
  76.         System.out.println("二分查找被调用~");
  77.         // 当 left > right 时，说明递归整个数组，但是没有找到
  78.         if (left >right){
  79.             return new ArrayList<Integer>();
  80.         }
  81.         int mid = (left + right) / 2;
  82.         int midVal = arr[mid];
  84.         if (findVal > midVal){//向右递归
  85.             return binarySearch2(arr,mid + 1,right,findVal);
  86.         }else if (findVal < midVal){//向左递归
  87.             return binarySearch2(arr, left, mid - 1, findVal);
  88.         }else {
  89.             List<Integer> resultIndexList = new ArrayList<>();
  90.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  91.             int temp = mid -1;
  92.             while (true){
  93.                 if (temp < 0 || arr[temp] != findVal) {
  94.                     break;
  95.                 }
  96.                 //否则，就temp 放入到 resIndexlist
  97.                 resultIndexList.add(temp);
  98.                 temp--;
  99.             }
  100.             resultIndexList.add(mid);
  102.             //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  103.             temp = mid + 1;
  104.             while (true){
  105.                 if (temp > arr.length - 1 || arr[temp] != findVal) {
  106.                     break;
  107.                 }
  108.                 resultIndexList.add(temp);
  109.                 temp++;
  110.             }
  111.             return resultIndexList;
  112.         }
  113.     }
  114. }

4、斐波那契(黄金分割)查找image.png
image.png

代码：

  1. package com.luyi.DataStructures.recursion;
  3. import java.lang.reflect.Array;
  4. import java.util.Arrays;
  6. /**
  7.  * 斐波那契查找
  8.  */
  9. public class FibonacciSearch {
  10.     public static int maxSize = 20;
  11.     public static void main(String[] args) {
  12.         int[] arr = {1,8,10,89,1000,1234};
  13.         System.out.println(fibSearch(arr, 1234));// 5
  14.     }
  15.     // 因为后面我们mid = low+F(k - 1)-1. 需要使用斐波那契数列, 因此我们需要先获取到斐波那契数列
  16.     // 用非递归的方法得到一个大小为20的斐波那契数列
  17.     public static int[] fbn(){
  18.         int[] f = new int[maxSize];
  19.         f[0] = 1;
  20.         f[1] = 1;
  21.         for (int i = 2; i < maxSize; i++){
  22.             f[i] = f[i - 1] + f[i - 2];
  23.         }
  24.         return f;
  25.     }
  27.     // 非递归的方式编写斐波那契数列查找算法
  29.     /**
  30.      *
  31.      * @param a
  32.      * @param key 需要查找的值
  33.      * @return 返回对应的下标 没有则返回-1
  34.      */
  35.     public static int fibSearch(int[] a, int key){
  36.         int low = 0;
  37.         int high = a.length -1;
  38.         int k = 0; // 表示斐波那契分割数值的下标  mid = low+F(k - 1)-1
  39.         int mid = 0;
  40.         int[] f = fbn(); // 获取斐波那契数列
  41.         // 获取斐波那契分割数值的下标
  42.         while (high > f[k]-1){
  43.             k++;
  44.         }
  45.         // 因为 f[k] 可能大于数组a 的长度 需要一个Array类 构造一个新的数组 并指向temp[]
  46.         int[] temp = Arrays.copyOf(a, f[k]); // 多出来的部分用0补起来
  47.         // 实际上需要使用a最后的数填充temp
  48.         // 举例 :
  49.         // temp:{1,8,10,89,1000,1234,0,0} =>temp:{1,8,10,89,1000,1234,1234,1234}
  50.         for (int i = high + 1;i < temp.length; i++){
  51.             temp[i] = a[high];
  52.         }
  54.         // 使用while循环查找我们的key
  55.         while (low <= high) {
  56.             mid = low + f[k-1]-1;
  57.             if (key < temp[mid]){//说明应该向数组的前一部分查找(左边)
  58.                 high = mid -1;
  59.                 // 为什么是k--
  60.                 // 1 全部元素 = 前面的元素 + 后边的元素
  61.                 // 2 f[k] = f[k-1] + f[k-2];
  62.                 // 因为前面有f[k-1]个元素,所以我们继续拆分   f[k-1] = f[k-2] + f[k-3];
  63.                 // 即在f[k-1] 的前面继续查找 k--
  64.                 // 即下次在循环的时候 mid = f[k-1-1] -1
  65.                  k--;
  66.             }else if ( key > temp[mid]){ // 我们继续向数组的右边查找
  67.                 low = mid + 1;
  68.                 // 为什么是k-2
  69.                 // 1 全部元素 = 前面的元素 + 后边的元素
  70.                 // 2 f[k] = f[k-1] + f[k-2];
  71.                 // 3 因为后面有f[k-2] 所以加足拆分 f[k -2] = f[k-3] + f[k-4];
  72.                 // 4 即在f[k-2] 的前面继续查找
  73.                 // 下次循环mid = f[k-1-2] -1
  74.                 k -= 2;
  75.             }else { // 找到
  76.                 // 需要确定返回的是哪个下标
  77.                 if (mid <= high){
  78.                     return mid;
  79.                 }else {
  80.                     return high;
  81.                 }
  82.             }
  83.         }
  84.         return -1; // 没有找到
  86.     }
  87. }