分块查找

#include<iostream>
using namespace std;
int fenkuai_search(int A[],int n,int m,int key)
{
    int max=0;//用来记录每个索引块中的最大值 
    int M=0;
    int B[n/m-1];//建立索引表数组；
    int j=0; 
    for(int i=0;i<n;i++)//寻找每一个索引块中的最大值； 
    {
        M++;
        if(M<=m&&A[i]>max) 
           max=A[i];
        if(M==m)
        {
            B[j]=max;
            j++;
            M=0;
        }
    }
    for(int i=0;i<n/m;i++)//在索引表中查找索引块 
    {
        if(key<=B[i])//找到对应的索引块 
        {
            for(int x=i*m;x<(i+1)*m;x++)//在对应的索引块中查找key； 
            {
                if(A[x]==key) return x;
            }
        }
     } 
     return -1;
}
int main()//举例用法 
{
    int A[]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};
    int key;
    cin>>key;
    int x=fenkuai_search(A,18,3,key); 
    if(x!=-1) cout<<key<<"元素所在的位置为："<<x;
    else cout<<"该数组中没有该元素"; 
    return 0;
}