查找算法——索引查找

一、索引查找

1.1.索引查找简介

• 索引查找又称为分块查找，其实是顺序查找和二分查找的结合，时间复杂度在二者之间
• 整个表中的元素未必有序，但划分若干块后，每一块中的元素为有序的

 

索引查找时的存储结构。索引查找需要对数据列表建立一个主表和一个索引表。

1. 主表：既要查找的序列
2. 索引表：索引项的集合

1.2.索引查找思路

💡💡思路：

1. 查找索引表。由于索引表是有序表，可采用二分查找或顺序查找，以确定查找的节点在哪一块。
2. 在已确定的块中进行顺序查找。由于主表分块内为无序状态，进行顺序查找

• 根据上图我们分析如下：

1. 主表R中，第1块中最大关键字22小于第2块中最小关键字24，第2块中最大关键字48小于第3块中最小关键字49，第3块中的最大关键字是86。

2. 如果我们查找关键字key＝24。

   • 首先将key依次与索引表中各个关键字进行比较。找到索引表第1个关键字的值小于K值，因此节点不在主表第1块中。
   • 由于key＜48，所以关键字为24的节点如果存在的话，则必定在第2块中。然后找到第2块的起始地址为7，从该地址开始在主表R[7…12]中进行顺序查找，直到R[11]＝key为止。
   1. 查找任何元素都是如此，先确定区间。再进行查找，如果该块中查找不成功，因此说明表中不存在关键字为30的节点，给出出错提示。这样大大提高了查找效率！

1.3.时间复杂度

索引查找的时间效率介于顺序查找和二分查找之间O(log2n)~O(n)

1.4.空间复杂度

索引查找每次分块不唯一，需要的储存空间也不确定

1.5.代码实现

C++代码：

#include <stdio.h>
//定义块的结构
struct index    
{
    //块的关键字
    int key;    
    //块的起始值
    int start;
    //块的结束值   
    int end;   
}index_table[4];    
int block_search(int key,int a[])    
{
    int i,j;
    i=1;
    // 确定在哪个块中
    while(i<=3 && key>index_table[i].key)   
        i++;
     // 大于分得的块数，则返回0
    if(i>3)    
        return 0;
    //j等于块范围的起始值
    j=index_table[i].start;   
    //在确定的块内进行顺序查找
    while(j<=index_table[i].end&&a[j]!=key)  
        j++;
    //  如果大于块范围的结束值，则说明没有要査找的数，j=0
    if(j>index_table[i].end)  
        j = 0;
    return j;
}
int main() 
{
    int i,j=0,k;
    int a[18] = {22, 12, 13, 3, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};/
    int key = 12;
    for(i=1;i<=3;i++)
    {
        //确定每个块范围的起始值
        index_table[i].start=j+1;    
        j=j+1;
        //确定每个块范围的结束值
       index_table[i].end=j+4;    
        j=j + 4;
        //确定每个块范围中元素的最大值
        index_table[i].key=a[j];    
    }
    k = block_search(key,a); 
    if(k!=0)
    {
        printf("查找位置是：%d\n",k);    
    }
    else
    {
        printf("查找失败!");    
    }
    return 0;
}

1.6.优缺点

优点：

块内记录随意存放，插入或删除较容易，无须移动大量记录。

缺点：

增加了一个辅助数组的存储空间，以及初始表的分块排序运算。