• Java面试干货：关于数组查找的几个常用实现算法

    查找算法在我们的面试和开发中，是很常见的一种算法，今天我就给大家介绍几个常用的查找算法。

    一. 线性查找

    1.概念

    线性查找也叫顺序查找，这是最基本的一种查找方法。该算法是从给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需的元素为止。在线下查找中，元素序列的排列可以有序，也可以无序。

    2.代码实现

    1. public class Test01 {
    2.         public static void main(String[] args) {
    3.                 //线性查找
    4.                 
    5.                 int[] arr = {45, 62, 15,62, 78, 30};
    6.                 
    7.                 int index = sequentialSearch01(arr, 62);
    8.                 System.out.println("指定元素首次出现的下标位置：" + index);
    9.                 
    10.                 List<Integer> indexList = sequentialSearch02(arr, 62);
    11.                 System.out.println("指定元素出现的下标位置的集合：" + Arrays.toString(indexList.toArray()));
    12.         }
    13.         
    14.         /**
    15.          * 顺序查找
    16.          * 返回指定元素首次出现的下标位置
    17.          */
    18.         public static int sequentialSearch01(int[] arr,int value){
    19.                 for (int i = 0; i < arr.length; i++) {
    20.                         if(arr[i] == value){
    21.                                 return i;
    22.                         }
    23.                 }
    24.                 return -1;
    25.         }
    26.         
    27.         /**
    28.          * 顺序查找
    29.          * 返回指定元素出现的下标位置的集合
    30.          */
    31.         public static List<Integer> sequentialSearch02(int[] arr,int value){
    32.                 List<Integer> list = new ArrayList<>();
    33.                 for (int i = 0; i < arr.length; i++) {
    34.                         if(arr[i] == value){
    35.                                 list.adds(i);
    36.                         }
    37.                 }
    38.                 return list;
    39.         }
    40. }

    二. 二分法查找

    1.概念

    二分查找(Binary Search)算法，也叫折半查找算法。当要从一个序列中查找一个元素的时候，二分查找是一种非常快速的查找算法。二分查找是针对有序数据集合的查找算法，如果是无序数据集合就遍历查找。

    二分查找之所以快速，是因为它在匹配不成功的时候，每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快，而不像顺序查找那样，每次仅能排除一个元素。

    2.原理

    比如有一个有序表数组[1,3,5,7,9,11,13,15,17,19,21]，它是按照从小到大的顺序来进行排列的，现在需要在该有序表中查找元素19，步骤如下：

    1.首先设置两个指针low和high，分别指向数据集合的第一个数据元素1(位序为0)和最后一个数据元素21(位序为10)。

    2.然后把整个数据集合长度分成两半，并用一个指针指向它们的临界点，所以定义指针mid指向了中间元素11(位序5)，也就是说mid=(high+low)/2，其中high和low都代表所指向的元素的位序，如下图：

    3.接着，将mid所指向的元素(11)与待查找元素(19)进行比较。因为19大于11，说明待查找的元素(19)一定位于mid和high之间。所以继续折半，则low = mid+1，而mid = (low+high)/2，结果如下图：

    4.接着，又将mid所指向的元素(17)与待查找元素(19)进行比较，由于19大于17，所以继续折半，则low = mid+1，而mid = (low+high)/2，结果如下图：

    5.最后，又将mid所指向的元素(19)与待查找元素(19)进行比较，结果相等，则查找成功，返回mid指针指向的元素的位序。

    如果查找的元素值不是19，而是20，那么在最后一步之前还得继续折半查找，最后出现的情况如下图：

    3.代码实现

    1. public class Test01 {
    2.         public static void main(String[] args) {
    3.                 //二分法查找
    4.  
    5.                 int[] arr = {1,2,3,4,5,6,7,8,9,11,11,11,11,11,11};
    6.  
    7.                 int index = binarySearch01(arr, 11);
    8.                 System.out.println("指定元素出现的下标位置：" + index);
    9.  
    10.                 List<Integer> indexList = binarySearch02(arr, 11);
    11.                 System.out.println("指定元素出现的下标位置的集合：" + Arrays.toString(indexList.toArray()));
    12.  
    13.                 index = recursionbinarySearch01(arr, 0, arr.length-1, 11);
    14.                 System.out.println("递归方式 - 指定元素出现的下标位置：" + index);
    15.  
    16.                 indexList = recursionbinarySearch02(arr, 0, arr.length-1, 11);
    17.                 System.out.println("递归方式 - 指定元素出现的下标位置的集合：" + Arrays.toString(indexList.toArray()));
    18.         }
    19.  
    20.         /**
    21.          * 有序的数组中查找某个元素出现的下标位置
    22.          * 不使用递归的二分查找
    23.          * 返回出现的下标位置
    24.          */
    25.         public static int binarySearch01(int[] arr,int val){
    26.  
    27.                 int low = 0;
    28.                 int high = arr.length-1;
    29.  
    30.                 while(low <= high){
    31.                         int mid = (low + high)/2;
    32.  
    33.                         if(val > arr[mid]){
    34.                                 //目标在右侧
    35.                                 low = mid+1;
    36.                         }else if(val < arr[mid]){
    37.                                 //目标在左侧
    38.                                 high = mid-1;
    39.                         }else{
    40.                                 return mid;
    41.                         }
    42.                 }
    43.                 return -1;
    44.         }
    45.  
    46.         /**
    47.          * 有序的数组中查找某个元素首次出现的下标位置
    48.          * 不使用递归的二分查找
    49.          * 返回下标集合
    50.          */
    51.         public static List<Integer> binarySearch02(int[] arr,int val){
    52.  
    53.                 int low = 0;
    54.                 int high = arr.length-1;
    55.  
    56.                 while(low <= high){
    57.                         int mid = (low + high)/2;
    58.  
    59.                         if(val > arr[mid]){
    60.                                 //目标在右侧
    61.                                 low = mid+1;
    62.                         }else if(val < arr[mid]){
    63.                                 //目标在左侧
    64.                                 high = mid-1;
    65.                         }else{
    66.                                 // 定义放置索引下标的集合
    67.                                 List<Integer> list = new ArrayList<>();
    68.                                 // 将首次查找的位置放入集合
    69.                                 list.add(mid);
    70.  
    71.                                 // 判断是否还有重复值
    72.                                 int index = mid + 1;
    73.                                 while(index < arr.length){
    74.                                         if(arr[index] == val){
    75.                                                 list.add(index);
    76.                                         }else{
    77.                                                 break;
    78.                                         }
    79.                                         index++;
    80.                                 }
    81.                                 index = mid-1;
    82.                                 while(index >= 0){
    83.                                         if(arr[index] == val){
    84.                                                 list.add(index);
    85.                                         }else{
    86.                                                 break;
    87.                                         }
    88.                                         index--;
    89.                                 }
    90.                                 return list;
    91.                         }
    92.                 }
    93.                 return null;
    94.         }
    95.  
    96.         /**
    97.          * 有序的数组中查找某个元素出现的下标位置
    98.          * 使用递归的二分查找
    99.          * 返回出现的下标位置
    100.          */
    101.         public static int recursionbinarySearch01(int[] arr,int low,int high,int val){
    102.  
    103.                 if(val < arr[low] || val > arr[high] || low > high){
    104.                         return -1;
    105.                 }
    106.  
    107.                 int mid = (low + high)/2;
    108.  
    109.                 if(val > arr[mid]){
    110.                         //目标在右侧
    111.                         return recursionbinarySearch01(arr, mid+1, high, val);
    112.                 }else if(val < arr[mid]){
    113.                         //目标在左侧
    114.                         return recursionbinarySearch01(arr, low, mid-1, val);
    115.                 }else{
    116.                         return mid;
    117.                 }
    118.         }
    119.         
    120.         /**
    121.          * 有序的数组中查找某个元素首次出现的下标位置
    122.          * 使用递归的二分查找
    123.          * 返回下标集合
    124.          */
    125.         public static List<Integer> recursionbinarySearch02(int[] arr,int low,int high,int val){
    126.  
    127.                 if(val < arr[low] || val > arr[high] || low > high){
    128.                         return null;
    129.                 }
    130.  
    131.                 int mid = (low + high)/2;
    132.  
    133.                 if(val > arr[mid]){
    134.                         //目标在右侧
    135.                         return recursionbinarySearch02(arr, mid+1, high, val);
    136.                 }else if(val < arr[mid]){
    137.                         //目标在左侧
    138.                         return recursionbinarySearch02(arr, low, mid-1, val);
    139.                 }else{
    140.                         // 定义放置索引下标的集合
    141.                         List<Integer> list = new ArrayList<>();
    142.                         // 将首次查找的位置放入集合
    143.                         list.add(mid);
    144.  
    145.                         // 判断是否还有重复值
    146.                         int index = mid + 1;
    147.                         while(index < arr.length){
    148.                                 if(arr[index] == val){
    149.                                         list.add(index);
    150.                                 }else{
    151.                                         break;
    152.                                 }
    153.                                 index++;
    154.                         }
    155.             
    156.                         index = mid-1;
    157.                         while(index >= 0){
    158.                                 if(arr[index] == val){
    159.                                         list.add(index);
    160.                                 }else{
    161.                                         break;
    162.                                 }
    163.                                 index--;
    164.                         }
    165.                         return list;
    166.                 }
    167.         }
    168. }

    4.优缺点

    优点:速度快，不占空间，不开辟新空间缺点:必须是有序的数组，数据量太小没有意义

    三. 插值查找

    1.概念

    从折半查找中可以看出，折半查找的查找效率还是不错的。可是为什么要折半呢？为什么不是四分之一、八分之一呢？

    举个例子，如果我们要在英语词典中查找“hello”这个单词，会首先翻开字典的中间部分，然后继续折半吗？肯定不会，对于查找单词“hello”，我们肯定是下意识的往字典的最前部分翻去，而查找单词“zero”则相反，我们会下意识的往字典的最后部分翻去。

    所以在折半查找法的基础上进行改造就出现了插值查找法，也叫做按比例查找。所以插值查找与折半查找唯一不同的是在于mid的计算方式上，它的计算方式为：

    int mid = low + (high - low) * (val- arr[low]) / (arr[high] - arr[low])

    这样就能快速定位目标数值所在的索引，比二分查找可以更快速实现查找。

    自适应获取mid，也就是自适应查找点。

    2.代码实现

    1. public class Test01 {
    2.         public static void main(String[] args) {
    3.                 //插值查找
    4.                 
    5.                 int[] arr = {1,2,3,4,5,6,7,8,9,11,11,11,11,11,11};
    6.  
    7.                 int index = insertSearch01(arr, 11);
    8.                 System.out.println("指定元素出现的下标位置：" + index);
    9.  
    10.                 List<Integer> indexList = insertSearch02(arr, 11);
    11.                 System.out.println("指定元素出现的下标位置的集合：" + Arrays.toString(indexList.toArray()));
    12.  
    13.                 index = recursionInsertSearch01(arr, 0, arr.length-1, 11);
    14.                 System.out.println("递归方式 - 指定元素出现的下标位置：" + index);
    15.  
    16.                 indexList = recursionInsertSearch02(arr, 0, arr.length-1, 11);
    17.                 System.out.println("递归方式 - 指定元素出现的下标位置的集合：" + Arrays.toString(indexList.toArray()));
    18.         }
    19.  
    20.         /**
    21.          * 有序的数组中查找某个元素出现的下标位置
    22.          * 不使用递归的二分查找
    23.          * 返回出现的下标位置
    24.          */
    25.         public static int insertSearch01(int[] arr,int val){
    26.  
    27.                 int low = 0;
    28.                 int high = arr.length-1;
    29.  
    30.                 while(low <= high){
    31.                         
    32.                         int mid = low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);
    33.  
    34.                         if(val > arr[mid]){
    35.                                 //目标在右侧
    36.                                 low = mid+1;
    37.                         }else if(val < arr[mid]){
    38.                                 //目标在左侧
    39.                                 high = mid-1;
    40.                         }else{
    41.                                 return mid;
    42.                         }
    43.                 }
    44.                 return -1;
    45.         }
    46.  
    47.         /**
    48.          * 有序的数组中查找某个元素首次出现的下标位置
    49.          * 不使用递归的二分查找
    50.          * 返回下标集合
    51.          */
    52.         public static List<Integer> insertSearch02(int[] arr,int val){
    53.  
    54.                 int low = 0;
    55.                 int high = arr.length-1;
    56.  
    57.                 while(low <= high){
    58.                         int mid = low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);
    59.  
    60.                         if(val > arr[mid]){
    61.                                 //目标在右侧
    62.                                 low = mid+1;
    63.                         }else if(val < arr[mid]){
    64.                                 //目标在左侧
    65.                                 high = mid-1;
    66.                         }else{
    67.                                 // 定义放置索引下标的集合
    68.                                 List<Integer> list = new ArrayList<>();
    69.                                 // 将首次查找的位置放入集合
    70.                                 list.add(mid);
    71.  
    72.                                 // 判断是否还有重复值
    73.                                 int index = mid + 1;
    74.                                 while(index < arr.length){
    75.                                         if(arr[index] == val){
    76.                                                 list.add(index);
    77.                                         }else{
    78.                                                 break;
    79.                                         }
    80.                                         index++;
    81.                                 }
    82.                                 index = mid-1;
    83.                                 while(index >= 0){
    84.                                         if(arr[index] == val){
    85.                                                 list.add(index);
    86.                                         }else{
    87.                                                 break;
    88.                                         }
    89.                                         index--;
    90.                                 }
    91.                                 return list;
    92.                         }
    93.                 }
    94.                 return null;
    95.         }
    96.  
    97.         /**
    98.          * 有序的数组中查找某个元素出现的下标位置
    99.          * 使用递归的二分查找
    100.          * 返回出现的下标位置
    101.          */
    102.         public static int recursionInsertSearch01(int[] arr,int low,int high,int val){
    103.  
    104.                 if(val < arr[low] || val > arr[high] || low > high){
    105.                         return -1;
    106.                 }
    107.  
    108.                 int mid = low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);
    109.  
    110.                 if(val > arr[mid]){
    111.                         //目标在右侧
    112.                         return recursionInsertSearch01(arr, mid+1, high, val);
    113.                 }else if(val < arr[mid]){
    114.                         //目标在左侧
    115.                         return recursionInsertSearch01(arr, low, mid-1, val);
    116.                 }else{
    117.                         return mid;
    118.                 }
    119.         }
    120.         
    121.         /**
    122.          * 有序的数组中查找某个元素首次出现的下标位置
    123.          * 使用递归的二分查找
    124.          * 返回下标集合
    125.          */
    126.         public static List<Integer> recursionInsertSearch02(int[] arr,int low,int high,int val){
    127.  
    128.                 if(val < arr[low] || val > arr[high] || low > high){
    129.                         return null;
    130.                 }
    131.  
    132.                 int mid = low + (high - low) * (val - arr[low])/(arr[high] - arr[low]);
    133.  
    134.                 if(val > arr[mid]){
    135.                         //目标在右侧
    136.                         return recursionInsertSearch02(arr, mid+1, high, val);
    137.                 }else if(val < arr[mid]){
    138.                         //目标在左侧
    139.                         return recursionInsertSearch02(arr, low, mid-1, val);
    140.                 }else{
    141.                         // 定义放置索引下标的集合
    142.                         List<Integer> list = new ArrayList<>();
    143.                         // 将首次查找的位置放入集合
    144.                         list.add(mid);
    145.  
    146.                         // 判断是否还有重复值
    147.                         int index = mid + 1;
    148.                         while(index < arr.length){
    149.                                 if(arr[index] == val){
    150.                                         list.add(index);
    151.                                 }else{
    152.                                         break;
    153.                                 }
    154.                                 index++;
    155.                         }
    156.                         index = mid-1;
    157.                         while(index >= 0){
    158.                                 if(arr[index] == val){
    159.                                         list.add(index);
    160.                                 }else{
    161.                                         break;
    162.                                 }
    163.                                 index--;
    164.                         }
    165.                         return list;
    166.                 }
    167.         }
    168. }

    四. 斐波那契查找

    1.概念

    斐波那契查找也叫做黄金分割法查找，这种查找法其实也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

    2.原理

    对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如元素个数为89的有序列表，89在斐波那契数列中是34和55相加所得。

    把元素个数为89的有序列表分成：前55个数据元素组成的前半段和34个数据元素组成的后半段。那么前半段元素个数和整个有序表长度的比值接近黄金比值0.618，而前后两段长度的比值也接近黄金比值0.618。

    假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败。这样斐波那契数列就被应用到查找算法中了。

    总长度=f[k]，前半段长度=f[k-1]，后半段长度=f[k-2]

    有序列表的元素个数不是斐波那契数列中的数字时该如何处理呢？

    当有序表的元素个数不是斐波那契数列中的某个数字时，需要把有序列表的长度补齐，让它成为斐波那契数列中的一个数值。

    如果不是补齐，而是将多余的截掉是否可行？把原有序列表截断肯定是不可行的，因为可能把要查找的目标值截掉。

    每次取斐波那契数列中的某个值时(f[k])，都会进行-1操作，这是因为数组下标从0开始。

    3.代码实现

    1. public class Test01 {
    2.         public static void main(String[] args) {
    3.                 
    4.                 int[] arr = {1,13,25,37,49,51,62,68,70,80,80};
    5.                 
    6.                 List<Integer> fiboSearchList = fiboSearchList(arr, 80);
    7.                 System.out.println(Arrays.toString(fiboSearchList.toArray()));
    8.         }
    9.         
    10.         public static List<Integer> fiboSearchList(int[] arr, int val) {
    11.                 
    12.                 int low = 0;
    13.                 int high = arr.length-1;
    14.                 
    15.                 // 斐波那契的索引下标。数组长度的数值在斐波那契数列中对应的索引下标
    16.                 int[] fiboArray = getFiboArray(10);//[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    17.                 
    18.                 // 斐波那契的索引下标。数组长度的数值在斐波那契数列中对应的索引下标
    19.                 int k = 0;
    20.                 // 斐波那契的索引下标。数组长度的数值在斐波那契数列中对应的索引下标
    21.                 while(arr.length > fiboArray[k]){
    22.                         k++;
    23.                 }
    24.                 System.out.println("k = " + k);//6
    25.                 System.out.println("fiboArray = " + Arrays.toString(fiboArray));//[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
    26.                 
    27.                 // 利用Java工具类Arrays 构造新数组并指向 数组 arr[]
    28.                 int[] temp = Arrays.copyOf(arr, fiboArray[k]);
    29.                 System.out.println("temp=" + Arrays.toString(temp));
    30.         //[1, 13, 25, 37, 49, 51, 62, 68, 70, 80, 80, 0, 0]
    31.                 
    32.                 //对新构造的数组进行元素补充，补充为最高位的数值
    33.                 for (int i = high+1; i < temp.length; i++) {
    34.                         temp[i] = arr[high];
    35.                 }
    36.                 System.out.println("补充数值的temp=" + Arrays.toString(temp));
    37.         //[1, 13, 25, 37, 49, 51, 62, 68, 70, 80, 80, 80, 80]
    38.                 
    39.                 while(low <= high){
    40.                         
    41.                         //数列左侧有f[k-1]个元素
    42.                         int mid = low + fiboArray[k-1] - 1;
    43.                         
    44.                         if(val < temp[mid]){
    45.                                 // 目标值小于mid所在元素，在左侧查找
    46.                                 high = mid-1;
    47.                                 
    48.                                 /*全部元素=前部元素+后部元素
    49.                  * f[k]=f[k-1]+f[k-2]
    50.                  * 因为左侧有f[k-1]个元素，所以可以继续拆分f[k-1]=f[k-2]+f[k-3]
    51.                  * 即在f[k-1]的前部继续查找 所以k-=1
    52.                  * 即下次循环 mid=f[k-1-1]-1
    53.                  */
    54.                                 k-=1;
    55.                         }else if(val > temp[mid]){
    56.                                 // 目标值大于mid所在元素，在右侧查找
    57.                                 low = mid+1;
    58.                                 
    59.                                 /*全部元素=前部元素+后部元素
    60.                  * f[k]=f[k-1]+f[k-2]
    61.                  * 因为右侧有f[k-2]个元素，所以可以继续拆分f[k-2]=f[k-3]+f[k-4]
    62.                  * 即在f[k-2]的前部继续查找 所以k-=2
    63.                  * 即下次循环 mid=f[k-1-2]-1
    64.                         */
    65.                                 k -= 2;
    66.                                 
    67.                         }else{
    68.                                 
    69.                                 // 定义放置索引下标的集合
    70.                                 ArrayList<Integer> list = new ArrayList<>();
    71.                                 list.add(mid);
    72.                                 
    73.                                 int index = mid+1;
    74.                                 while(index < arr.length){
    75.                                         if(arr[index] == val){
    76.                                                 list.add(index);
    77.                                                 index++;
    78.                                         }else{
    79.                                                 break;
    80.                                         }
    81.                                 }
    82.                                 index = mid-1;
    83.                                 while(index > 0){
    84.                                         if(arr[index] == val){
    85.                                                 list.add(index);
    86.                                                 index--;
    87.                                         }else{
    88.                                                 break;
    89.                                         }
    90.                                 }
    91.                                 return list;
    92.                         }
    93.                 }
    94.                 return null;
    95.         }
    96.         
    97.         public static int[] getFiboArray(int maxSize){
    98.                 
    99.                 int[] fiboArray = new int[maxSize];
    100.                 
    101.                 fiboArray[0] = 1;
    102.                 fiboArray[1] = 1;
    103.                 
    104.                 for (int i = 2; i < fiboArray.length; i++) {
    105.                         fiboArray[i] = fiboArray[i-1] + fiboArray[i-2];
    106.                 }
    107.                 return fiboArray;
    108.         }
    109. }

  • 相关阅读:
    计算机毕业设计Java校园生活信息服务平台(源码+系统+mysql数据库+Lw文档）
    YOLO目标检测——树叶检测数据集下载分享【含对应voc、coco和yolo三种格式标签】
    RS232通讯转485通讯接线心得
    易知微防洪“四预”智慧水利平台上线！全面助力智慧水利建设发展
    台积电嘲讽英特尔CEO：不可能超越我们了，安心退休吧
    Hfish安全蜜罐部署
    EMQX 企业版正式上架华为云 OSC，助力企业实现云原生MQTT消息服务器的全生命周期管理
    【机器学习】逻辑回归LR的推导及特性是什么，面试回答？
    移动端页面如何优雅的适配各种屏幕，包括PC端
    【吴恩达机器学习笔记】八、应用机器学习的建议
  • 原文地址：https://blog.csdn.net/finally_vince/article/details/127884638