(1)分块查找
①、原则1:
前一块中的最大数据,小于后一块中的所有数据。(块内无序,块间有序)
②、原则2:
块数数量一般等于数字的个数开根号。例如,16个数字一般分为4块左右。
③、核心思路
先确定要查找的元素在哪一块,然后在块内挨个查找。
(2)分块查找的基本查找

查找30
块代码的书写

在内存中,就会生成如下的索引表

查找步骤:
先用二分查找找max的值,发现第三块的max值大于30,就在第三块的索引范围内查找数字30的索引。
(3)分块查找的扩展查找—无规律的数据

面对无序的数据,也可以分块,但是块与块之间的数据范围(即min~max)不能有交集。
比如查找48,去比较每一块数据的范围,最后确定在第五块,再在第五块的索引范围中查找数字为48的索引。
(4)分块查找的扩展查找—查找的过程中还需要添加数据,即哈希查找

由于要存100个数字,对100开根号,可以分成10块,每一块的范围依次递增。
当获取20时,20的范围在1-100之间,所以丢到块1;如果又生成了一个40,40也属于块1,但是块1零索引已经有数据为20,此时可以把40挂在20的后面。
如果遇到块中已经有的数据,先判断该数据的范围属于哪一块,再把数据放到块中的索引范围进行查找,一样就重新获取,不一样就存储好之后进行下一次获取。

