devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java面试干货：关于数组查找的几个常用实现算法_.java有序数组查找

作者：IT小白 | 2024-08-08 08:06:11

赞

踩

.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. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/947006
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号