经典算法之分块查找法（Java实现）

活动地址：21天学习挑战赛

文章目录

一、算法

1.算法概述

2.算法步骤

3.算法特点

二、算法实践

1.Java代码

2.执行结果

三、复杂度分析

1.时间复杂度

2.空间复杂度

---

一、算法

1.算法概述

        分块查找法（Blocking Search）又称为索引顺序查找法，在此查找法中，除了原表本身以外还需要建立一个“索引表”，即将原表分成一块一块，每一块选取其最大的记录作为关键字项，块中的起始下标为块的指针项。索引表按照关键字有序，即块与块之间有序，块内元素无序。查找时先确定待查找的记录在哪一块，再在具体某个块内使用顺序查找法查找其具体位置。故其性能介于顺序查找法和折半查找法之间。

相关文章链接：

• 经典算法之顺序查找法 
• 经典算法之折半查找法

2.算法步骤

1. 首先确定待查记录所在的块（子表）
2. 然后在块中进行顺序查找确定记录的最终位置

 以上图为例，假设要查找记录key=38：

• 先将key依次与索引表中各个最大关键字进行比较。因为22<38<44 则关键字为38的记录若存在则必定在第二个块（子表）中
• 然后从第二个块的起始下标之间使用顺序查找法查找key的具体位置，最终查找成功返回其下标：7   ；若查找失败则返回失败标识：-1

（注：以上图片来源于教材《数据结构简明教程》） 

3.算法特点

优点：

• 在表中插入和删除元素时，只需要找到对应的块，就可以在块内进行插入和删除运算
• 块内无序，插入和删除都较为容易，无需进行大量移动
• 适合线性表既要快速查找又要经常动态变化的场景

缺点：

• 需要增加一个存储索引表的内存空间
• 需要对初始索引表按照其最大关键字（或最小关键字）进行排序运算

 

---

 

二、算法实践

1.Java代码

package TwentyOne_Challenge;
import java.util.Scanner;
public class DayNine {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        //原表
        int a[]={9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82};
        //分块获得对应的索引表,这里是一个以索引结点为元素的对象数组
        BlockTable [] arr={
                new BlockTable(22,0,3),//最大关键字为22 起始下标为0,3的块
                new BlockTable(44,4,7),
                new BlockTable(60,8,11),
                new BlockTable(82,12,15)
        };
        //打印原表
        System.out.print("原表元素如下：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        //待查关键字
        System.out.print("请输入你所要查询的关键字：");
        int key=input.nextInt();
        //调用分块查找算法，并输出查找的结果
        int result=BlockSearch(a,arr,key);
        System.out.print("查询结果为："+result);
    }
    private static int  BlockSearch(int a[],BlockTable[] arr,int key){
        int left=0,right=arr.length-1;
        //利用折半查找法查找元素所在的块
        while(left<=right){
            int mid=(right-left)/2+left;
            if(arr[mid].key>=key){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        //循环结束，元素所在的块为right+1 取对应左区间下标作为循环的开始点
        int i=arr[right+1].low;
        //在块内进行顺序查找确定记录的最终位置
        while(i<=arr[right+1].high&&a[i]!=key){
            i++;
        }
        //如果下标在块的范围之内，说明查找成功，佛否则失败
        if(i<=arr[right+1].high){
            return i;
        }else{
            return -1;
        }
    }
}
 
//索引表结点
class BlockTable{
    int key;
    int low;
    int high;
    BlockTable(int key,int low,int high){
        this.key=key;
        this.low=low;
        this.high=high;
    }
}

2.执行结果

 

 

---

 

三、复杂度分析

1.时间复杂度

不超过O(n)

2.空间复杂度

不超过O(n)