分块查找

1. 算法分析:

1.1. 平均查找长度 (ASL):

假设每个块中关键字数量相等 $\frac{块内数量+1}{2}+{\log }_2(块数+1)-1$

2. 适用范围:

1. 方便,快速地插入记录
2. 较为快速地查找关键字

2.1. 不适用范围:

1. 哈希表其实比分块查找更好用, 所以分块思想才是最重要的

3. 算法思想:

对无序的数据划分为不重不漏的若干分块, 要求块之间有序, 这些有序的块合称为索引表 查找的时候, 先在有序的块中找到关键字所属块 (一般使用折半查找法) 在块内使用顺序查找关键字

4. 在Java中的实现:

4.1. 梗概:

1. 块至少需要具备以下两个信息:
   1. 块中关键字的取值范围
      1. 每个块存储关键字的取值上限, 以前驱块的上限作为当前块的取值下限
   2. 块中关键字的储存位置
      1. 这个在Java中非常好办, 每个块中都用一个数组来存储其中的关键字, 该数组就是它们的存储位置
2. 查找块的方法

4.2. 代码:

import me.irfen.algorithm.ch01.ArrayList;
public class BlockSearch {
    private int[] index;
    private ArrayList[] list;
    /**
     * 初始化索引表
     * @param index
     */
    public BlockSearch(int[] index) {
        if (index != null && index.length != 0) {
            this.index = index;
            this.list = new ArrayList[index.length];
            for (int i = 0; i < list.length; i++) {
                list[i] = new ArrayList();
            }
        } else {
            throw new Error("index cannot be null or empty.");
        }
    }
   
    /**
     * 插入元素
     * @param value
     */
    public void insert(int value) {
        int i = binarySearch(value);
        list[i].add(value);
    }
   
    /**
     * 查找元素
     * @param data
     * @return
     */
    public boolean search(int data) {
        int i = binarySearch(data);
        for (int j = 0; j < list[i].size(); j++) {
            if (data == list[i].get(j)) {
                return true;
            }
        }
        return false;
    }
   
    /**
     * 打印每块元素
     */
    public void printAll() {
        for (int i = 0; i < list.length; i++) {
            ArrayList l = list[i];
            System.out.println("ArrayList " + i + ":");
            for (int j = 0; j < l.size(); j++) {
                System.out.println(l.get(j));
            }
        }
    }
   
    /**
     * 二分查找定位索引位置
     * @param data 要插入的值
     * @return
     */
    private int binarySearch(int data) {
        int start = 0;
        int end = index.length;
        int mid = -1;
        while (start <= end) {
            mid = (start + end) / 2;
            if (index[mid] > data) {
                end = mid - 1;
            } else {
                // 如果相等，也插入在后面
                start = mid + 1;
            }
        }
        return start;
    }
}