例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 }