分块查找C/C++代码实现

小咪咪 2023-02-21 04:59 14阅读 0赞

## 分块查找(索引顺序查找)： ##

这是一种性能介于顺序查找和折半查找之间的一种查找方法，是顺序查找和折半查找两种算法的简单合成。  
块内无序，块间有序  
所谓 “分块有序” 指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字。  
![在这里插入图片描述][20200628191502459.png]

## 算法适用情况： ##

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。 如果线性表既要快速查找又经常动态变化，则可采用分块查找。  
使用条件：线性表必须要能实现分块之间有序。

## 代码如下： ##

#include<stdio.h>
    
    //索引表
    typedef struct
    {
        
    	int key;	//最大关键字
    	int start;	//块开始下标
    	int end;	//块结束下标
    }Node;
    typedef struct
    {
        
    	Node idx[10];//表项
    	int len;	//表长
    }IdxTable;
    
    
    //分块查找
    IdxTable table;	//索引表
    int BlockingSearch(int key,int a[])
    {
        
    	//折半查找
    	int  low, high, mid;
    	low = 1;
    	high = table.len;
    	while (low <= high)
    	{
        
    		mid = (low + high) / 2;			//找到中间位置
    		if (key<=table.idx[mid].key)
    		{
        
    			//顺序查找
    			if (key <= table.idx[mid - 1].key)
    			{
        
    				high = mid - 1;
    			}
    			else
    			{
        
    						for (int i = table.idx[mid].start; i <= table.idx[mid].end; i++)
    						{
        
    							if (key == a[i])
    							{
        
    								return (i + 1);	//从1开始算起
    							}
    						}
    						return 0;
    			}
    			
    		}
    		else
    		{
        
    			low = mid + 1;				//如果小于查找的记录则重新定位mid指针
    		}
    	}
    	
    	return 0;
    }
    
    
    int main()
    {
        
    	int i;
    	int a[] = {
        22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53 };
    	//索引表
    	table.idx[1].key = 22; table.idx[1].start = 0; table.idx[1].end = 5;
    	table.idx[2].key = 48; table.idx[2].start = 6; table.idx[2].end = 11;
    	table.idx[3].key = 86; table.idx[3].start = 12; table.idx[3].end = 17;
    	table.len = 3;
    	
    	//查找结果
    	int key;
    	printf("请输入要查找的记录：");
    	scanf("%d", &key);
    	i = BlockingSearch(key, a);
    	printf("查找记录在表中的位置是（从1开始，0为未找到）：%d\n", i);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[20200628191502459.png]: https://img-blog.csdnimg.cn/20200628191502459.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628192314405.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70