【21天学习挑战赛】分块查找

​
​

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

怕什么真理无穷，进一步有一份的欢喜。

【21天学习挑战赛】分块查找

✌我为什么参与挑战赛

1，机缘

读到研一了，暑假假期打开私信发现这个挑战赛就鼓起勇气参加了。

2，期待的收获

A, 本人在华南理工大学攻读专硕，目前研究方向是图像恢复，从事深度学习相关工作，目标是从事Java后端开发。
B, 期待您的反馈，如果有什么不对的地方，欢迎指正！
C, 期待认识志同道合的领域同行或技术交流。
如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

🍉分块查找的图解

主数据：n个数的序列，通常直接存放在数组中，可以是任何顺序。
基于主数据建立的块索引表，索引表中的每个元素存储三个属性：关键字、块区间左端点、块区间右端点，索引表按关键字有序。

1. 将待排序的数组(n)进行分块，分为s块.
2. 块索引表按关键字有序，可以根据折半查找快速定位待查关键字所在块。
3. 然后再该块中顺序查找找到对应的num.

💬分块查找的定义

分块查找, 按块有序查找, 块间有序, 块内不必有序。 创建索引表, 先查找索引表找到块, 再块内查找元素。

✨分块查找的优劣

优势

分块查找可以看做是两次查找：分块的折半查找和分块内的顺序查找。最佳的时间复杂度为$O(\sqrt{n})$

劣势

需要额外建立索引表，是比较耗费空间的，属于是空间换时间的策略。

🍵分块查找的步骤

1. 建立索引
2. 通过二分查找确定块的位置，没找到返回-1
3. 顺序查找确定要查找元素位置，没找到返回-1

✍️ 算法实现

class BlockSearch {

    public static void main(String[] args) {
        // 主数据表
        int[] a = {9, 22, 12, 14, 35, 42, 44, 38, 48, 60, 58, 47, 78, 80, 77, 82};
        // 待查关键字
        int key = 48;
        // 分块后获得索引表
        Block[] t = {
                new Block(0, 3, 22),
                new Block(4, 7, 44),
                new Block(8, 11, 60),
                new Block(12, 15, 82)
        };
        // 调用算法,并输出结果
        int result = blocksSearch(t, a, key);
        System.out.println(result);
    }

    /**
     * @param blocks 块的索引表:块中的可以无序的,但是块与块之间是有序的
     *               例如:blocks[0]中的最大值小于blocks[1]中的最小值,依次类推
     * @param array  待查询的数组
     * @param num    待查找的值
     * @return num 在array数组中的索引位置:-1表示未找到
     */
    public static int blocksSearch(Block[] blocks, int array[], int num) {
        // 1.先从块的索引表中找出当前值所在的块
        int blockIndex = getBlockIndex(blocks, num);// 快的索引
        // -1表示块未找到,那么对应num的在array肯定找不到
        if (blockIndex == -1) {
            return -1;
        }
        System.out.println("num:" + num + " 可能在第 " + blockIndex + " 块中:[" + blocks[blockIndex].startIndex + "~"
                + blocks[blockIndex].endIndex + "]");
        // 2.在块中使用顺序查找.
        // 使用顺序来扫描整个块
        int start = blocks[blockIndex].startIndex;
        int end = blocks[blockIndex].endIndex;
        while (start <= end && array[start] != num) {
            start++;
        }
        // 如果i没有超出块的范围，说明找到
        if (start <= end) {
            // 返回对应的位置
            return start;
        } else {
            // 未找到时返回-1
            return -1;
        }
    }


    /**
     * 查找num所在的块,比较的是Block中的maxNum
     *
     * @param blocks
     * @param num
     * @return -1表示未找到所在块
     */
    private static int getBlockIndex(Block[] blocks, int num) {
        // 1.使用二分查找 找到num所在块的位置
        int low = 0;
        int high = blocks.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) >> 1;
            // 2.表示找到的值等于当前块的最大值,那么直接返回当前索引即可
            if (num == blocks[mid].maxNum) {
                return mid;
            } else if (num > blocks[mid].maxNum) {
                low = mid + 1;
            } else if (num < blocks[mid].maxNum) {
                high = mid - 1;
            }
        }
        // 3.元素所在块为：low
        int resultIndex = low;
        if (resultIndex >= blocks.length) {
            resultIndex = -1;// 表示未找到
        }
        return resultIndex;
    }

}

class Block {
    int maxNum;// 块中的最大值
    int startIndex;// 块在数组中的起始索引位置
    int endIndex;// 块在数组中的结束索引位置

    public Block(int startIndex, int endIndex, int maxNum) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.maxNum = maxNum;
    }

    @Override
    public String toString() {
        StringBuilder sBuilder = new StringBuilder();
        sBuilder.append("[").append(startIndex).append("~").append(endIndex).append("]");
        sBuilder.append(" maxNum=").append(maxNum);
        return sBuilder.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！