七大查找算法（Java版）_java查找算法-程序员宅基地
技术标签： 算法 java 二分查找 【数据结构与算法基础】
文章目录
前言
在非数值运算问题中，数据存储量一般很大，为了在大量信息中找到某些值，需要用到查找技术，为了提高查找效率，需要对一些数据进行排序。查找和排序的数据处理量占有非常大的比重，故查找和排序的有效性直接影响到算法的性能，因而查找和排序是重要的处理技术。
几个与查找有关的基本概念：
查找表：由同一类型的数据元素构成的集合。由于数据元素之间存在着完全松散的关系，因此查找表是一种非常灵活的结构，可以利用任意数据结构实现。
关键字：数据元素的某个数据项的值，用它可以标识查找表中一个或一组数据元素。如果一个关键字可以唯一标识查找表中的一个数据元素，则称其为 主关键字，否则为次关键字。当数据元素仅有一个数据项时，其关键字即为该数据元素的值。
查找：根据给定的关键字值，在查找表中确定一个关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。若找到相应数据元素，则称查找成功，否则称查找失败，此时返回空地址。
平均查找长度：为确定数据元素在查找表中的位置，需要和给定的值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于长度为n的查找表，查找成功时的平均查找长度：
查找两种常见的分类：
| 类别 | 特点 |
|---|---|
| 静态查找 | 只做查找操作的查找表，即： 1、查询某个“特定的”数据元素是否在表中 2、检索某个“特定的”数据元素和各种属性 |
| 动态查找 | 在查找中同时进行插入或删除等操作 |
| 类别 | 特点 |
|---|---|
| 无序查找 | 被查找数列有序无序均可 |
| 有序查找 | 被查找数列为有序数列 |
查找算法有七种，分别为：顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找。
基于线性结构的查找，有两种最常见的查找方法：顺序查找和折半查找。
- 顺序查找
顺序查找的特点是，用所给的关键字与线性表中各元素的关键字逐个进行比较，直到成功或失败。 - 折半查找
折半查找又称为二分查找，这种查找方法需要待查的查找表满足两个条件：首先，查找表必须使用顺序的存储结构；其次，查找表必须按关键字大小有序排列。算法的基本思想是：首先，将查找表中间位置数据元素的关键字与给定关键字比较，如果相等则查找成功；否则利用中间元素将表一分为二，如果中间元素关键字大于给定关键字，则在前一子表中进行折半查找，否则在后一子表中进行折半查找。重复以上过程，直到找到满足条件的元素，则查找成功；或直到子表为空为止，此时查找不成功。
一、顺序查找
1.1 顺序查找介绍
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。
- 基本思路
从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。 - 复杂度分析
查找成功时的平均查找长度为： ASL = 每个元素被查找的概率 * 总的元素的个数=1/n*(1+2+3+…+n) = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n)，所以，顺序查找的时间复杂度为O(n)。 - 优缺点
缺点：是当n 很大时，平均查找长度较大，效率低；
优点：是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。
1.2 顺序查找实现
用Java代码实现顺序查找，示例代码如下：
private static int sequenceSearch(int[] array,int target){
for(int i=0;i<array.length;i++){
if(target==array[i])
return i;
}
return -1;
}
1.3 顺序查找优化
在算法中，比较和赋值是比较耗时的。在上个章节的顺序查找实现代码中，存在着数组下标和目标值两种比较，那么能不能转变为一种比较呢？答案是可以的，不过要进行数据预处理，将查找值也放到数列中。比如将要查找的元素放在原数列中的第一位或最后一位(如果需要扩容就进行扩容)。此处将要查找的目标元素放在第一位，预处理示例代码如下：
int[] array = {
12,3,43,5,9};
int target = 43;
int[] newArray = new int[array.length+1];
newArray[0] = target;
for(int i=0;i<array.length;i++){
newArray[i+1] = array[i];
}
也许有人会问，这样预处理一遍数据，需要将数组中所有数组都移动一遍，岂不是更花费时间？从总体上来看，确实是这样的。但是，面临大量的数据要处理时，常常要进行预处理、清洗等操作，这样会令纯粹处理数据（在该例子中就是搜索固定元素）的时间编的更少，更有效。当数据进行预处理后，搜索时就可以不用再比较两次，示例代码如下：
public static int sequenceSearchPlus(int[] arr,int key){
int n=arr.length-1;
arr[0]=key;
while(arr[n]!=key){
n--;
}
return n;
}
完整的测试代码如下：
public class BasicTest {
public static void main(String[] args){
int[] array = {
12,3,43,5,9};
int target = 43;
int[] newArray = new int[array.length+1];
newArray[0] = target;
for(int i=0;i<array.length;i++){
newArray[i+1] = array[i];
}
int result = sequenceSearchPlus(newArray,target)-1;
if(result != -1){
System.out.println("要查找的元素,在数组中的下标是："+result);
}else{
System.out.println("要查找的元素不在数组中");
}
}
public static int sequenceSearchPlus(int[] arr,int key){
int n=arr.length-1;
arr[0]=key;
while(arr[n]!=key){
n--;
}
return n;
}
}
测试结果为：
要查找的元素,在数组中的下标是：2
二、二分查找
2.1 二分查找介绍
二分查找，是一种在有序数组中查找某一特定元素的查找算法。
- 基本思路
用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。 - 复杂度分析
假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。被查找区间的大小变化为：n, n/2, n/4, n/8, …, n/(2k)。
可以看出来，这是一个等比数列。其中 n/(2^k)=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过n/(2^k)=1 ，我们可以求得 k=log2n ，所以时间复杂度就是 O(logn)。
空间复杂度：O(1)。 - 优缺点分析
当查找表不会频繁有更新、删除操作时，使用折半查找是比较理想的。如果查找表有较频繁的更新、删除操作，维护表的有序会花费比较大的精力，不建议使用该查找方式。
2.2 二分查找实现
用Java代码实现折半查找，有两种方式：迭代法和递归法。迭代法示例代码如下：
static int binarySearch1(int arr[],int len,int target){
/*初始化左右搜索边界*/
int left=0,right=len-1;
int mid;
while(left<=right){
/*中间位置：两边界元素之和/2向下取整*/
mid=(left+right)/2;
/*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
if(target<arr[mid]){
right=mid-1;
/*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
}else if(target>arr[mid]){
left=mid+1;
/*搜索到对应元素*/
}else if(target==arr[mid]){
return mid;
}
}
/*搜索不到返回-1*/
return -1;
}
递归法示例代码如下：
static int binarySearch2(int array[],int left,int right,int target){
if(left<=right){
int mid=(left+right)/2;
/*搜索到对应元素*/
if(array[mid]==target){
return mid;
}else if(array[mid]<target){
/*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
return binarySearch2(array,mid+1,right,target);
}else{
/*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
return binarySearch2(array,left,mid-1,target);
}
}else{
return -1;
}
}
2.3 二分查找变体
二分查找算法四种常见的变形问题，分别是：
- 查找第一个值等于给定值的元素。
- 查找最后一个值等于给定值的元素。
- 查找第一个大于等于给定值的元素。
- 查找最后一个小于等于给定值的元素。
- 1、查找第一个值等于给定值的元素
public static int search(int[] nums, int val) {
int n = nums.length;
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] < val) {
low = mid + 1;
} else if (nums[mid] > val) {
high = mid - 1;
} else {
// 如果nums[mid]是第一个元素，或者nums[mid-1]不等于val
// 说明nums[mid]就是第一个值为给定值的元素
if (mid == 0 || nums[mid - 1] != val) {
return mid;
}
high = mid - 1;
}
}
return -1;
}
- 2、查找最后一个值等于给定值的元素
public static int search(int[] nums, int val) {
int n = nums.length;
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] < val) {
low = mid + 1;
} else if (nums[mid] > val) {
high = mid - 1;
} else {
// 如果nums[mid]是最后一个元素，或者nums[mid+1]不等于val
// 说明nums[mid]就是最后一个值为给定值的元素
if (mid == n - 1 || nums[mid + 1] != val) {
return mid;
}
low = mid + 1;
}
}
return -1;
}
- 3、查找第一个大于等于给定值的元素
public static int search(int[] nums, int val) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] < val) {
low = mid + 1;
} else {
// 如果nums[mid]是第一个元素，或者nums[mid-1]小于val
// 说明nums[mid]就是第一个大于等于给定值的元素
if (mid == 0 || nums[mid - 1] < val) {
return mid;
}
high = mid - 1;
}
}
return -1;
}
- 4、查找最后一个小于等于给定值的元素
public static int search(int[] nums, int val) {
int n = nums.length;
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] > val) {
high = mid - 1;
} else {
// 如果nums[mid]是最后一个元素，或者nums[mid+1]大于val
// 说明nums[mid]就是最后一个小于等于给定值的元素
if (mid == n - 1 || nums[mid + 1] > val) {
return mid;
}
low = mid + 1;
}
}
return -1;
}
三、插值查找
3.1 插值查找介绍
在二分查找中，每次都是从待查找序列的中间点开始查找，这样的做法在正确性上固然没什么问题，但假如要查找的值距离某个边界比较近，还从中间点开始查找，就有点浪费时间了。举个例子来说说明，假如在在一个{1,2…,100}的数组中，要查找88这个值，还一直采用和中间点比较的策略，就显得不太明智，因为明显可以明显从较为靠后的位置去检索。为了克服这种弊端， 引入了插值查找。
- 基本思路
插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，其核心就在于插值的计算公式 (key-array[low])/(array[high]-array[low])*(high-low)。简而言之，基于二分查找算法，将查找点的选择改进为自适应选择。 - 复杂度分析
时间复杂性：如果元素均匀分布，则O(log(logn))，在最坏的情况下可能需要O(n)。
空间复杂度：O(1)。 - 优缺点分析
对于长度比较长、关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
3.2 插值查找实现
上面的说法是总体介绍，落实到具体代码上的话，再慢慢分析。在二分查找中，mid的计算方式如下：
将low从分数中提取出来，mid的计算就变成了：
在插值查找中，mid的计算方式转换成了：
有了上面的算术，就可以写代码了，迭代法插值查找示例代码如下：
private static int insertSearch1(int arr[],int target){
/*初始化左右搜索边界*/
int left=0,right=arr.length-1;
int mid;
while(left<=right){
mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
/*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
if(target<arr[mid]){
right=mid-1;
/*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
}else if(target>arr[mid]){
left=mid+1;
/*搜索到对应元素*/
}else if(target==arr[mid]){
return mid;
}
}
/*搜索不到返回-1*/
return -1;
}
递归法插值查找示例代码如下：
private static int insertSearch2(int array[],int left,int right,int target){
if(left<=right){
int mid=left+(target-array[left])/(array[right]-array[left])*(right-left);
/*搜索到对应元素*/
if(array[mid]==target){
return mid;
}else if(array[mid]<target){
/*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/
return insertSearch2(array,mid+1,right,target);
}else{
/*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/
return insertSearch2(array,left,mid-1,target);
}
}else{
return -1;
}
}
四、斐波那契查找
4.1 斐波那契查找介绍
和前面的二分查找、插值查找相比，斐波那契查找是类似的，不过换了一种寻找mid点的方法。顾名思义，该种查找方法中，使用到了斐波那契数列，斐波那契数列的形式是：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。
- 基本思路
在斐波那契数列中的元素满足这样的关系：F[k]=F[k-1]+F[k-2]，此处将这个数组稍微改一下，改成：（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1，图示如下：
通过上面的图，应该就可以看出为什么要这样分割数组了，因为要找出一个中间mid值，以便将数组按斐波那契数列的规律，分割成两部分。 - 复杂度分析
最坏情况下，时间复杂度为O(logn)，且其期望复杂度也为O(logn)。
4.2 斐波那契查找实现
上面介绍了分割的方法，但还有一个问题，就是斐波那契数列中的数值都是固定的，但要查找的数组的长度不固定，这样情况要怎么办？此时需要的是创建新数组，使新数组的长度是斐波那契数列中的值，并且是比原数组长度略大的值（此处只能是略大，因为略小的话，就会导致原数组元素丢失），多出来的元素用原数组最高位元素补充，示例代码如下：
int high = arr.length - 1;
int f[] = fib();
/*获取最相邻的斐波那契数组中元素的值，该值略大于数组的长度*/
while(high > f[k] - 1) {
k++;
}
/*因为 f[k]值可能大于arr的长度。如果大于时，需要构造一个新的数组temp[]，将arr数组中的元素拷贝过去，不足的部分会使用0填充*/
int[] temp=Arrays.copyOf(arr, f[k]);
/*然后将temp后面填充的0，替换为最后一位数字
*如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/
for(int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
解决了如何分割、如果创建临时新数组后，还有一个问题：怎么判断最后target == arr[i]时，这个arr[i]是原来的数组中的元素，还是在新数组中扩展出来的元素？如果是新数组中扩展出来的元素，该元素的下标是大于原数组元素的最大下标的，肯定不是要寻找的位置。其实该问题容易解决，就是当target == arr[i]时，如果arr[i]的下标>原数组最大下标时，直接返回元数组最大下标即可。示例代码如下：
/*原arr数组中的值*/
if(mid <= high){
return mid;
/*在temp中，扩展出来的高位的值*/
}else{
return high;
}
完整斐波那契查找示例代码如下：
public class FibonacciSearch {
public static int FLENGTH = 20;
public static void main(String[] args) {
int [] arr = {
1,8,10,89,100,134};
int target = 89;
System.out.println("目标元素在数组中位置是：" + fibSearch(arr, target));
}
public static int[] fib() {
int[] f = new int[FLENGTH];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < FLENGTH; i++) {
f[i] = f[i-1] + f[i-2];
}
return f;
}
public static int fibSearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
int k = 0;
int mid = 0;
int f[] = fib();
/*获取最相邻的斐波那契数组中元素的值，该值略大于数组的长度*/
while(high > f[k] - 1) {
k++;
}
/*因为 f[k]值可能大于arr的长度。如果大于时，需要构造一个新的数组temp[]，将arr数组中的元素拷贝过去，不足的部分会使用0填充*/
int[] temp=Arrays.copyOf(arr, f[k]);
/*然后将temp后面填充的0，替换为最后一位数字
*如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/
for(int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
while (low <= high) {
mid = low + f[k - 1] - 1;
if(target < temp[mid]) {
high = mid - 1;
/*因为f[k]=f[k-1]+f[k-2]，所以k--就相当于取temp数组的左边部分*/
k--;
} else if ( target > temp[mid]) {
low = mid + 1;
/*同理，f[k]=f[k-1]+f[k-2]，k -= 2就相当于取temp数组的右边部分*/
k -= 2;
} else {
/*原arr数组中的值*/
if(mid <= high){
return mid;
/*在temp中，扩展出来的高位的值*/
}else{
return high;
}
}
}
return -1;
}
}
五、树表查找
基于树的查找方法是将待查表组织成特定的树结构，并在树结构的基础上实现查找的方法。
5.1 二叉树查找
二叉排序树（二叉查找树）是最简单的树表查找算法，该算法需要利用待查找的数据，进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，然后再进行查找。
- 二叉排序树的性质
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
1>若左子树不空，则左子树上所有结点的键值均小于或等于它的根结点的键值。
2>若右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值。
3>左、右子树也分别为二叉排序树。
5.1.1 二叉排序树中序遍历
二叉排序树有不同的遍历方式，中序遍历的结果比较直观。二叉树示例：
二叉树上中序遍历的方式是：左节点、根节点、右节点。该二叉树的遍历结果为：1、3、4、6、7、8、10、13、14。
5.1.2 二叉树查找实现
- 1、创建二叉树
首先，要创建一个树的节点，节点中要有该节点储存的值，然后起左右子树。示例代码：
class BinaryTree{
int value;
BinaryTree left;
BinaryTree right;
public BinaryTree(int value){
this.value = value;
}
}
接下来就要创建二叉排序树，创建二叉排序树是一个递归的过程，需要将序列中的值一个一个添加到二叉树中。方便起见，可以利用序列中第一个元素作为根节点，再持续添加节点，示例代码：
int[] array = {
35,76,6,22,16,49,49,98,46,9,40};
BinaryTree root = new BinaryTree(array[0]);
for(int i = 1; i < array.length; i++){
createBST(root, array[i]);
}
具体创建树的过程，就是一个不断与根节点比较，然后添加到左侧、右侧或不添加的过程。因为在二叉排序树中，不存在重复元素，有相等元素已经在树中时，直接忽略后续相等元素。示例代码：
public static void createBST(BinaryTree root, int element){
BinaryTree newNode = new BinaryTree(element);
if(element > root.value){
if(root.right == null)
root.right = newNode;
else
createBST(root.right, element);
}else if(element < root.value){
if(root.left == null)
root.left = newNode;
else
createBST(root.left, element);
}else{
System.out.println("该节点" + element + "已存在");
return;
}
}
- 2、二叉树查找
查找元素是否在树中的过程，就是一个二分查找的过程，不过查找的对象从左右子序列转换成了左右子树而已。示例代码：
public static void searchBST(BinaryTree root, int target, BinaryTree p){
if(root == null){
System.out.println("查找"+target+"失败");
}else if(root.value == target){
System.out.println("查找"+target+"成功");
}else if(root.value >= target){
searchBST(root.left, target, root);
}else{
searchBST(root.right, target, root);
}
}
完整示例代码：
public class BinarySortTree {
public static void main(String[] args) {
int[] array = {
35,76,6,22,16,49,49,98,46,9,40};
BinaryTree root = new BinaryTree(array[0]);
for(int i = 1; i < array.length; i++){
createBST(root, array[i]);
}
System.out.println("中序遍历结果：");
midOrderPrint(root);
System.out.println();
searchBST(root, 22, null);
searchBST(root, 100, null);
}
/*创建二叉排序树*/
public static void createBST(BinaryTree root, int element){
BinaryTree newNode = new BinaryTree(element);
if(element > root.value){
if(root.right == null)
root.right = newNode;
else
createBST(root.right, element);
}else if(element < root.value){
if(root.left == null)
root.left = newNode;
else
createBST(root.left, element);
}else{
System.out.println("该节点" + element + "已存在");
return;
}
}
/*二叉树中查找元素*/
public static void searchBST(BinaryTree root, int target, BinaryTree p){
if(root == null){
System.out.println("查找"+target+"失败");
}else if(root.value == target){
System.out.println("查找"+target+"成功");
}else if(root.value >= target){
searchBST(root.left, target, root);
}else{
searchBST(root.right, target, root);
}
}
/*二叉树的中序遍历*/
public static void midOrderPrint(BinaryTree rt){
if(rt != null){
midOrderPrint(rt.left);
System.out.print(rt.value + " ");
midOrderPrint(rt.right);
}
}
}
测试结果为：
该节点49已存在
中序遍历结果：
6 9 16 22 35 40 46 49 76 98
查找22成功
查找100失败
六、分块查找
6.1 分块查找介绍
分块查找，顾名思义，要先将所有元素按大小进行分块，然后在块内进行查找。在分块时，块内的元素不一定是有序的，只要一个块内的元素在同一区间就行。用较标准的语言描述是：算法的思想是将n个数据元素"按块有序"划分为m块（m≤n）。每一块中的结点不必有序，但块与块之间必须"按块有序"，每个块内的的最大元素小于下一块所有元素的任意一个值。
所以，在使用分块查找时，分成了两步：
1>找到元素可能在的块。
2>在对应的块内查找元素。
6.2 分块查找实现
在上个章节说到，该方法要先分块，那么块应该具有怎样的属性呢？至少要有以下元素：
1>长度
一般是固定的长度。
2>起始位置
当块的长度固定后，需要确定起始位置才能固定不同的块表示的元素的位置范围。
3>块标识
该标识用来标识块内元素的范围，可以用最大值、最小值、平均值等多种方式来表示。
示例代码如下：
public class Block {
/*block的索引，用来标识块中元素*/
public int index;
/*该block的开始位置*/
public int start;
/*块元素长度，在该例子中0代表空元素，不计入block长度*/
public int length;
public Block(int index, int start, int length) {
this.index = index;
this.start = start;
this.length = length;
}
}
在该例子中，定义元素数组和块数组，示例如下：
/*主表*/
static int[] valueList = new int[]{
104, 101, 103, 105,102, 0, 0, 0, 0, 0,
201, 202, 204, 203,0, 0, 0, 0, 0, 0,
303, 301, 302, 0, 0, 0, 0, 0, 0, 0
};
/*索引表*/
static Block[] indexList = new Block[]{
new Block(1, 0, 5),
new Block(2, 10, 4),
new Block(3, 20, 3)
};
valueList中的0，可以简单理解为块内的空元素；indexList中的1,2,3代表块内元素的取值范围，第一个块内是100-200之间的元素，第2个块内是200-300之间的元素，以此类推。
在进行元素查找时，先判断是否存在元素可能存在的块。示例如下：
/*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
int index = key/100;
/*找到对应的block*/
for(int i = 0;i < indexList.length; i++) {
if(indexList[i].index == index) {
indexItem = indexList[i];
break;
}
}
/*如果数组中不存在对应的块，则返回-1，查找失败*/
if(indexItem == null)
return -1;
找到内对的块后，就在该块内进行搜索，示例代码如下：
/*在对应的block中查找*/
for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) {
if(valueList[i] == key)
return i;
}
return -1;
}
如果需要在数组中插入元素，同样需要需要先查找是否存在对应的块，如果存在，则追加到该块中元素的尾部。
完整示例代码如下：
public class BlockSearch {
/*主表*/
static int[] valueList = new int[]{
104, 101, 103, 105,102, 0, 0, 0, 0, 0,
201, 202, 204, 203,0, 0, 0, 0, 0, 0,
303, 301, 302, 0, 0, 0, 0, 0, 0, 0
};
/*索引表*/
static Block[] indexList = new Block[]{
new Block(1, 0, 5),
new Block(2, 10, 4),
new Block(3, 20, 3)
};
public static void main(String[] args) {
System.out.println("原始主表：");
printElemts(valueList);
/*分块查找*/
int searchValue = 203;
System.out.println("元素"+searchValue+"，在列表中的索引为："+blockSearch(searchValue)+"\n");
/*插入数据并查找*/
int insertValue = 106;
/*插入成功，查找插入位置*/
if (insertBlock(insertValue)) {
System.out.println("插入元素"+insertValue+"后的主表：");
printElemts(valueList);
System.out.println("元素" + insertValue + "在列表中的索引为：" + blockSearch(insertValue));
}
}
public static void printElemts(int[] array) {
for(int i = 0; i < array.length; i++){
System.out.print(array[i]+" ");
if ((i+1)%10 == 0) {
System.out.println();
}
}
}
/*插入数据*/
public static boolean insertBlock(int key) {
Block item = null;
/*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
int index = key/100;
int i = 0;
/*找到对应的block*/
for (i = 0; i < indexList.length; i++) {
if (indexList[i].index == index) {
item = indexList[i];
break;
}
}
/*如果数组中不存在对应的块，则不能插入该数据*/
if (item == null) {
return false;
}
/*将元素插入到每个块的最后*/
valueList[item.start + item.length] = key;
/*更新该块的长度*/
indexList[i].length++;
return true;
}
public static int blockSearch(int key) {
Block indexItem = null;
/*确定插入到哪个块中，在该例子中，第一个block中放的是100-200之间的数，第二个block中放的是200-300之间的数，以此类推*/
int index = key/100;
/*找到对应的block*/
for(int i = 0;i < indexList.length; i++) {
if(indexList[i].index == index) {
indexItem = indexList[i];
break;
}
}
/*如果数组中不存在对应的块，则返回-1，查找失败*/
if(indexItem == null)
return -1;
/*在对应的block中查找*/
for(int i = indexItem.start; i < indexItem.start + indexItem.length; i++) {
if(valueList[i] == key)
return i;
}
return -1;
}
}
测试结果如下：
原始主表：
104 101 103 105 102 0 0 0 0 0
201 202 204 203 0 0 0 0 0 0
303 301 302 0 0 0 0 0 0 0
元素203，在列表中的索引为：13
插入元素106后的主表：
104 101 103 105 102 106 0 0 0 0
201 202 204 203 0 0 0 0 0 0
303 301 302 0 0 0 0 0 0 0
元素106在列表中的索引为：5
七、哈希查找
7.1 哈希查找介绍
要了解哈希查找，就要先了解一下哈希表和哈希函数。先看下标准的定义：哈希表，是根据关键值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表（哈希表）。
从上面的定义可以看出：哈希查找与线性表查找和树表查找最大的区别在于，不用数值比较。
7.1.1 构造哈希表
要使用哈希查找，就要先有哈希表，所以需要先介绍一下哈希表的构造方法。常见的构造方法有如下几种：
- 1、直接定址法
哈希地址：f(key) = a*key+b (a、b为常数)。
这种方法的优点是：简单、均匀、不会产生冲突。但是需要事先知道 key 的分布情况，适合查找表较小并且连续的情况。 - 2、数字分析法
假设关键字是R进制数（如十进制）。并且哈希表中可能出现的关键字都是事先知道的，则可选取关键字的若干数位组成哈希地址。选取的原则是使得到的哈希地址尽量避免冲突，即所选数位上的数字尽可能是随机的。
举个例子：比如11位手机号码“136xxxx5889”，其中前三位是接入号，一般对应不同运营公司的子品牌，中间四位表示归属地，最后四位才是用户号，此时就可以用后4位来作为哈希地址。 - 3、平方取中法
取key平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，仅取其中的几位为地址不一定合适。而一个数平方后的中间几位数和数的每一位都相关， 由此得到的哈希地址随机性更大。如key是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。 - 4、折叠法
折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表的表长，取后几位作为 f(key) 。
比如key是9876543210，哈希表的表长为3位，我们将 key 分为4组，987 | 654 | 321 | 0 ，然后将它们叠加求和 987+654+321+0=1962，再取后3位即得到哈希位置是：962 。 - 5、除留余数法
取关键字被某个不大于哈希表表长 m 的数 p 除后所得的余数为哈希地址。即 f(key) = key % p (p ≤ m)。这种方法是最常用的哈希函数构造方法。 - 6、随机数法
哈希地址：random(key) ，这里random是随机函数，当 key 的长度不等时，采用这种方法比较合适。
7.1.2 解决冲突
在使用以上方法计算key对应的哈希地址时，难免会遇到两个key不相等，到计算出来的哈希地址相同的情况，该情况就被称为“冲突”。在构造哈希表，常用如下方式解决冲突：
- 1、开放定址法
该方法指的是两个key在计算出相同的哈希地址时，后者继续在哈希表中向后寻找空位置，存放改key的方法。举个例子：假如原始的key中有8、15两个元素，哈希表中的长度为7，当使用key % length求余时，两个key会计算出相同的哈希位置。假设哈希表中的1位置已经存放了8，那么15就要从1位置往后寻找空位，假如2位置是空的，就可以把15存放到2位置；假如2位置不空，就要往3位置寻找，以此类推。 - 2、拉链法
该方法中处理相同位置的方式是：创建一个List，存储相同位置上不同值的key，此处借用网上的一张图来表示：
7.2 哈希查找实现
依据上文介绍，先构建哈希表。而要构建哈希表，就要先有计算地址的方法，示例代码如下：
/*用除留余数法计算要插入元素的地址*/
public static int hash(int[] hashTable, int data) {
return data % hashTable.length;
}
有了计算哈希地址的方法后，剩下的就是将原始的元素插入到哈希表中，也就是先利用key计算一个地址，如果这个地址以及有元素了，就继续向后寻找。此处可以循环计算地址，示例代码如下：
/*将元素插入到哈希表中*/
public static void insertHashTable(int[] hashTable, int target) {
int hashAddress = hash(hashTable, target);
/*如果不为0，则说明发生冲突*/
while (hashTable[hashAddress] != 0) {
/*利用开放定址法解决冲突，即向后寻找新地址*/
hashAddress = (++hashAddress) % hashTable.length;
}
/*将元素插入到哈希表中*/
hashTable[hashAddress] = target;
}
哈希表构建后，就是在哈希表中查找元素了。在查找元素时，容易想到的情况是：在直接计算出的哈希地址及其后续位置查找元素。特殊的是，上一步中，有循环计算地址的操作，所以此处计算到原始地址时，也代表查找失败。示例代码如下：
public static int searchHashTable(int[] hashTable, int target) {
int hashAddress = hash(hashTable, target);
while (hashTable[hashAddress] != target) {
/*寻找原始地址后面的位置*/
hashAddress = (++hashAddress) % hashTable.length;
/*查找到开放单元(未存放元素的位置)或 循环回到原点，表示查找失败*/
if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, target)) {
return -1;
}
}
return hashAddress;
}
完整示例代码如下：
public class HashSearch {
/*待查找序列*/
static int[] array = {
13, 29, 27, 28, 26, 30, 38};
/* 初始化哈希表长度，此处哈希表容量设置的和array长度一样。
* 其实正常情况下，哈希表长度应该要长于array长度，因为使用
* 开放地址法时，可能会多使用一些空位置
*/
static int hashLength = 7;
static int[] hashTable = new int[hashLength];
public static void main(String[] args) {
/*将元素插入到哈希表中*/
for (int i = 0; i < array.length; i++) {
insertHashTable(hashTable, array[i]);
}
System.out.println("哈希表中的数据：");
printHashTable(hashTable);
int data = 28;
System.out.println("\n要查找的数据"+data);
int result = searchHashTable(hashTable, data);
if (result == -1) {
System.out.println("对不起，没有找到！");
} else {
System.out.println("在哈希表中的位置是：" + result);
}
}
/*将元素插入到哈希表中*/
public static void insertHashTable(int[] hashTable, int target) {
int hashAddress = hash(hashTable, target);
/*如果不为0，则说明发生冲突*/
while (hashTable[hashAddress] != 0) {
/*利用开放定址法解决冲突，即向后寻找新地址*/
hashAddress = (++hashAddress) % hashTable.length;
}
/*将元素插入到哈希表中*/
hashTable[hashAddress] = target;
}
public static int searchHashTable(int[] hashTable, int target) {
int hashAddress = hash(hashTable, target);
while (hashTable[hashAddress] != target) {
/*寻找原始地址后面的位置*/
hashAddress = (++hashAddress) % hashTable.length;
/*查找到开放单元(未存放元素的位置)或 循环回到原点，表示查找失败*/
if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, target)) {
return -1;
}
}
return hashAddress;
}
/*用除留余数法计算要插入元素的地址*/
public static int hash(int[] hashTable, int data) {
return data % hashTable.length;
}
public static void printHashTable(int[] hashTable) {
for(int i=0;i<hashTable.length;i++)
System.out.print(hashTable[i]+" ");
}
}
测试结果：
哈希表中的数据：
27 29 28 30 38 26 13
要查找的数据28
在哈希表中的位置是：2
智能推荐
android studio 报错 AAPT: error: style attribute ‘attr/colorPrimary (aka com._aapt: error: attribute android:style not found.-程序员宅基地
文章浏览阅读1.7w次，点赞5次，收藏4次。是因为把这个 implementation 'androidx.appcompat:appcompat:1.2.0' 给删掉了。dependencies { implementation 'androidx.appcompat:appcompat:1.2.0'}_aapt: error: attribute android:style not found.
2023编程语言趋势_各程序设计语言最新发展趋势-程序员宅基地
文章浏览阅读3.5w次，点赞73次，收藏121次。Python持续霸榜，PHP依旧颓势，Java雄风不再，Rust热度不减，汇编迅速崛起，C语言地位稳固_各程序设计语言最新发展趋势
前方高能！2023开放原子开发者大会亮点攻略，一触即发-程序员宅基地
文章浏览阅读5.1k次，点赞25次，收藏22次。12月16-17日中国 · 无锡。
layui框架学习（35：数据表格_列参数设置）_layui表格-程序员宅基地
文章浏览阅读2.6k次。学习并记录layui框架中内置模块的数据表格模块中与列相关的主要参数设置方式。_layui表格
使用IntelliJ IDEA进行远程调试Flink大数据代码_使用intellij idea进行远程调试flink大数据代码 百度快照-程序员宅基地
文章浏览阅读367次。本文将介绍如何使用IntelliJ IDEA进行远程调试Flink代码的步骤，并提供相应的源代码示例。通过使用IntelliJ IDEA进行远程调试，我们可以方便地对Flink大数据代码进行调试和排查问题。本文介绍了使用IntelliJ IDEA进行远程调试Flink代码的步骤，并提供了一个简单的WordCount示例。在IntelliJ IDEA中，点击右上角的"Debug"按钮，选择之前创建的远程调试配置。在IntelliJ IDEA中，点击"Debug"按钮启动Flink作业。步骤4：启动远程调试。_使用intellij idea进行远程调试flink大数据代码 百度快照
Apache部署超详细教程-程序员宅基地
文章浏览阅读4.4w次，点赞57次，收藏429次。Apache服务器部署背景Apache与Nginx对比Apache的部署安装Apache的基础信息修改Apache默认配置修改默认端口修改默认发布文件修改默认发布目录Apache的虚拟主机如何配置虚拟主机排错思路Apache内部的访问控制基于IP基于用户背景百度百科：Apache是世界使用排名第一的Web服务器软件。它可以运行在几乎所有广泛使用的计算机平台上，由于其跨平台和安全性被广泛使用，..._apache部署
随便推点
Delphi-XE5-手势操作-Gestures-使用方法_delphi安卓添加手势-程序员宅基地
文章浏览阅读4.8k次。Delphi-XE5-手势操作-Gestures-使用方法一、首先转载一下别人的方法介绍：今天尝试了TTabControl的使用。在很多Android的app中，首次启动时都使用选项卡模式进行产品介绍，用户通过向左滑动，改变选项卡。在xe5下这项工作由TTabControl控件完成，如下图： 1、TTabControl外观TTabContro_delphi安卓添加手势
cut命令-程序员宅基地
文章浏览阅读3.9k次，点赞7次，收藏27次。cut命令_cut命令
Web3.0时代什么时候到来，Web3.0有什么机会？_社交网络 web3.0-程序员宅基地
文章浏览阅读6.1k次，点赞65次，收藏89次。什么是web3.0？web3.0和web2.0以及web1.0有什么不一样？web3.0需要哪些技术支撑？web3.0有哪些应用场景?web3.0什么时候到来？普通人有哪些机会？开发者需要掌握哪些开发技术？随着科技的飞速发展，互联网也在不断演变。从Web1.0到Web2.0，我们已经见证了互联网从单向信息传递到用户参与互动的转变。而现在，我们正站在迈向Web3.0时代的门槛上。今天本文就来探讨相关话题。_社交网络 web3.0
帆软报表 出现多余空白页_帆软打印出现空白页-程序员宅基地
文章浏览阅读1.1w次。. 描述若您的模板内容明明是一页就可以显示出来，但是分页预览时却出来两页，而第二页却没有数据是空白页，原因是您的模板中有多余的空白格没有删除。这种情况可能由两种原因引起，一种是空白单元格导致使其有多余的空白页，另外一种情况是制作的模板中有多余的空白sheet。2.问题的原因2.1空白单元格导致使其有多余的空白页示例：如：如下您在 H2 单元格填上数据并设置格式后，删除该..._帆软打印出现空白页
iframe中设置无滚动条_iframe无滚动条-程序员宅基地
文章浏览阅读3.6w次。1、只有水平滚动条： //auto、yesindex.html中：body{overflow-y:hidden;} //隐藏了垂直的2、只有垂直滚动条： //auto、yesindex.html中：body{overflow-x:hidden;} //隐藏了水平的3、水平、垂直都没有： //auto、yesindex.html中：body{o_iframe无滚动条
B站---【狂神说Java】JavaWeb入门到实战---笔记-程序员宅基地
文章浏览阅读10w+次，点赞1.2k次，收藏7.6k次。JavaWebJava Web1、基本概念web开发：·web，网页的意思，www.baidu.com·静态web。html,sss。提供给所有人看的数据始终不会发生变化！动态web。淘宝，几乎是所有的网站；。提供给所有人看的数据始终会发生变化，每个人在不同的时间，不同的地点看到的信息各不相同！。技术栈：Servlet/ISP，ASP，PHP..._狂神说jav