Java基本查找算法--分块查找

我不是女神ヾ 2023-10-06 03:00 206阅读 0赞

## `一、分块查找` ##

> 分块查找又称为索引查找，他是一种性能介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储线性表：将R\[0…n-1\]`均分`为b块，前b-1块中的记录个数为s=n/b，最后一块即第b块的记录小于等于s；`每块中的关键字（元素）不一定有序，但前一块中的最大关键字必须小于后一块的最小关键字，即要求表示“分块有序”的`；抽取各块中的最大关键字及其起始位置构成一个索引表IDX\[0…b-1\]，即IDX\[i\]（0<=i<=b）中存放着第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表示一个递增有序表。

> 分块查找的基本思想是：首先查找索引表，因为索引表是有序表，故可以采用二分查找或顺序查找，以确定待查记录在那一块；然后在已确定的块中进行顺序查找（因为内无序，只能用顺序查找）。如果在块中找到该记录则查询成功，否则查找失败。

> 示例：有如下数字构成的序列：A=\{8, 14, 6, 9, 10. 22, 34, 18, 19, 31, 40, 38, 54, 66, 46\}，请求分块查找算法查询给定的数值10是否存在，并输出结果。  
> 要利用分块查找算法查询给定的数值10，首先将原序列分成三块\{ \[8, 14, 6, 9, 10\], \[22, 34, 18, 19,31\], \[40, 38, 54, 66, 46\] \},对应的索引表为\{ \{14，0\}，\{34，5\}，\{66，10\}\}，而索引表里包含索引项（如\{34,5\}），每项内容包含每块最大关键字和索引块的开始位置。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]

public class SSTable {
        
    
        private int data[];
        private int length;
        public int searchIndex(IndexTable it, int m, SSTable st, int n, int k) {
        
            int low = 0, high = m -1, mid, i;
            int b = n/m;
            while (low <= high) {
        
                mid=(low + high) / 2;
                if (it.elem[mid].key >= k) {
        
                    high = mid - 1;
                } else {
        
                    low = mid + 1;
                }
            }
    
            if (low < m) {
        
                i = it.elem[low].start;
                while (i <= it.elem[low].start + b -1 && st.data[i] != k) {
        
                    i++;
                }
                if (i <= it.elem[low].start + b -1){
        
                    return i;
                } else {
        
                    return -1;
                }
            }
    
            return -1;
        }
    
        public void  createSSTable(int[] a){
        
            this.data = new int[a.length];
            for (int i = 0; i < a.length; i++) {
        
                this.data[i] = a[i];
                this.length++;
            }
        }
    
        /* 索引表结点 */
        public class IndexItem {
        
            public  int key;
            public  int start;
        }
    
        /* 索引表 */
         public class IndexTable{
        
            public  IndexItem[] elem;
            public int length = 0;
            public void createIndexTable(int[][] b){
        
                this.elem = new IndexItem[b.length];
                int i;
                for (i = 0; i < b.length; i++){
        
                    elem[i] = new IndexItem();
                    elem[i].key = b[i][0];
                    elem[i].start = b[i][1];
                    this.length++;
                }
            }
        }
    
        public static void main(String[] args) {
        
            int[] a = {
        8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46};
            int[][] b = {
        {
        14, 0},{
        34, 5},{
        66, 10}};
            SSTable st = new SSTable();
            IndexTable it = st.new IndexTable();
            st.createSSTable(a);
            it.createIndexTable(b);
            int x = st.searchIndex(it, b.length, st, a.length, 10);
            if (x < 0) {
        
                System.out.println("要查找的元素不存在");
            } else {
        
                System.out.println("查找成功，该元素在表中的位置为：" + (x + 1));
            }
        }
    
    }

> 算法分析：由于分块查找实际上是两次查找过程，因此整个查找过程的平均查找长度是两次查找的平均查找长度之和。若以二分查找来确定块，则分块查找成功时的平均查找长度为:ASLblk=ASLbn+ASLsq=1og2(h+1)-1+(s+1)/2≈1og2(n/s+1)+s/2,若以顺序查找确定块,则分块查找成功时的平均查找长度为: ASL’blk=ASLbn+ASLsq=(b+1)/2=s^2 + 2s+ 。显然,当s=`根号n`时,ASL’blk取极小值,即采用顺序查找确定块时,应将各块中的记录数选定为√n。如表中有记录1000条,则应把它分为100个块,每个块中包含100个记录。用分块查找平均要做100次比较，而顺序查找平均需要做5000次比较个奇找只需要14次比较。由此可见，分块查找算法的效率介于顺序查找和二分查找之间。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200619001658154.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3ODcwNDIx,size_16,color_FFFFFF,t_70