例26：分块查找

分块查找的概念我还是第一次了解，所以有点陌生，但所幸并不难，所以并没有卡在这里。

分块查找的理念就是分块，块内可以无序，块与块间必须有序，分两级查找，第一级查找所在块，第二级顺序查找块内元素，第一级查找可以用二分，但我的没有用。

看代码，更好理解：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 struct Block
 5 {
 6        int key;
 7        int start;
 8        int end;
 9 }blockArray[4];
10 
11 void BlockInit(int *pArray,int nCount)
12 {
13      int blockCount = (nCount%4 == 0?nCount/4:nCount/4+1);
14      int i;
15      for(i = 0;i<3;i++)
16      {
17              blockArray[i].start = i*4;
18              blockArray[i].end = i*4+3;
19              blockArray[i].key = pArray[i*4+3];
20      }
21      blockArray[i].start = i*4;
22      blockArray[i].end = nCount-1;
23      blockArray[i].key = pArray[nCount-1];
24      
25 }
26 
27 int BlockSearch(int key,int *pArray)
28 {
29      for(int i = 0;i<4;i++)
30      {
31              if(key <= blockArray[i].key)
32              {
33                     for(int j = blockArray[i].start;j<=blockArray[i].end;j++)
34                     {
35                             if(key == pArray[j])
36                             {
37                                    return j;
38                             }
39                     }
40                     return -1;
41              }
42      }
43      return -1;
44 }
45 
46 int main()
47 {
48     int pArray[20],nCount,key;
49     while(~scanf("%d",&nCount) && nCount)
50     {
51                                for(int i = 0;i<nCount;i++)
52                                {
53                                        scanf("%d",&pArray[i]);
54                                }
55                                scanf("%d",&key);
56                                BlockInit(pArray,nCount);
57                                for(int i = 0;i<4;i++)
58                                {
59                                        printf("
 start:%d
 key:%d
 end:%d
",blockArray[i].start,blockArray[i].key,blockArray[i].end);
60                                }
61                                int Pos = BlockSearch(key,pArray);
62                                printf("AnswerPos : %d
",Pos);
63     }
64     
65     return 0;
66 }