在Java中,数组是一种非常常用的数据结构。在开发中,经常需要对数组进行查找。因此,在本文中,将从多个方面详细阐述Java数组查找技巧。
一、线性查找
线性查找是一种基本的查找方法,也称为顺序查找。顾名思义,它的查找方式就是从数组的头开始,每次逐个元素进行比较,并且在相应的位置找到目标值时返回。这种查找方式适用于无序数组。
/** * 线性查找 * @param arr 数组 * @param key 待查找关键字 * @return 返回查找到的位置,未找到返回-1 */ public static int linearSearch(int[] arr, int key) { for (int i = 0; i < arr.length; i++) { if (arr[i] == key) { return i; } } return -1; }
二、二分查找
二分查找也称为折半查找,适用于有序数列。它的查找方式是将有序数组分为左右两个部分,每次比较中间位置的元素值,如果匹配则返回,否则缩小查找范围,重复此步骤,直到找到目标值或查找范围为空。
/** * 二分查找 * @param arr 数组 * @param key 待查找关键字 * @return 返回查找到的位置,未找到返回-1 */ public static int binarySearch(int[] arr, int key) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { low = mid + 1; } else { high = mid - 1; } } return -1; }
三、插值查找
插值查找是对二分查找的改进,适用于数值分布比较均匀的有序条件。它的查找方式是根据要查找的关键值key与数组的边界值arr[low]和arr[high]以及中间位置arr[mid]的关系,计算mid的值并且从mid位置开始逐步找到目标值位置。
/** * 插值查找 * @param arr 数组 * @param key 待查找关键字 * @return 返回查找到的位置,未找到返回-1 */ public static int interpolationSearch(int[] arr, int key) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]); if (arr[mid] == key) { return mid; } else if (arr[mid] < key) { low = mid + 1; } else { high = mid - 1; } } return -1; }
四、哈希查找
哈希查找是通过建立一个哈希表来实现查找的方式。哈希表的建立是通过对关键字进行哈希函数的计算,将关键字映射为数组的下标,然后将该关键字存储在对应的数组位置上。在查找时,根据哈希函数计算关键字的位置,判断该位置上的关键字是否匹配,如果匹配,则返回对应数组下标,否则在哈希表中继续查找。
/** * 哈希查找 * @param arr 数组 * @param key 待查找关键字 * @return 返回查找到的位置,未找到返回-1 */ public static int hashSearch(int[] arr, int key) { Mapmap = new HashMap<>(); for (int i = 0; i < arr.length; i++) { map.putIfAbsent(arr[i], i); } return map.getOrDefault(key, -1); }
五、小结
以上就是几种常见的Java数组查找技巧。选择适合自己的查找方法,可以提高查找效率,更好地完成任务。