1  public  class BlockSearch {
 2 
 3      class IndexType {
 4          public  int key;  //  分块中的最大值
 5          public  int link;  //  分块的起始位置
 6     }
 7 
 8      //  建立索引方法，n 是线性表最大长度，gap是分块的最大长度
 9      public IndexType[] createIndex( int[] list,  int n,  int gap) {
10          int i = 0, j = 0, max = 0;
11          int num = n / gap;
12         IndexType[] idxGroup =  new IndexType[num];  //  根据步长数分配索引数组大小
13 
14          while (i < num) {
15             j = 0;
16             idxGroup[i] =  new IndexType();
17             idxGroup[i].link = gap * i;  //  确定当前索引组的第一个元素位置
18             max = list[gap * i];  //  每次假设当前组的第一个数为最大值
19               //  遍历这个分块，找到最大值
20              while (j < gap) {
21                  if (max < list[gap * i + j]) {
22                     max = list[gap * i + j];
23                 }
24                 j++;
25             }
26             idxGroup[i].key = max;
27             i++;
28         }
29 
30          return idxGroup;
31     }
32 
33      //  分块查找算法
34      public  int blockSearch(IndexType[] idxGroup,  int m,  int[] list,  int n,  int key) {
35          int mid = 0;
36          int low = 0;
37          int high = m -1;
38          int gap = n / m;  //  分块大小等于线性表长度除以组数
39          
40           //  先在索引表中进行二分查找，找到的位置存放在 low 中
41          while (low <= high) {
42             mid = (low + high) / 2;
43              if (idxGroup[mid].key >= key) {
44                 high = mid - 1;
45             }  else {
46                 low = mid + 1;
47             }
48         }
49 
50          //  在索引表中查找成功后，再在线性表的指定块中进行顺序查找
51          if (low < m) {
52              for ( int i = idxGroup[low].link; i < idxGroup[low].link + gap; i++) {
53                  if (list[i] == key)
54                      return i;
55             }
56         }
57 
58          return -1;
59     }
60 
61      //  打印完整序列
62      public  void printAll( int[] list) {
63          for ( int value : list) {
64             System.out.print(value + " ");
65         }
66         System.out.println();
67     }
68 
69      //  打印索引表
70      public  void printIDX(IndexType[] list) {
71         System.out.println("构造索引表如下：");
72          for (IndexType elem : list) {
73             System.out.format("key = %d, link = %d\n", elem.key, elem.link);
74         }
75         System.out.println();
76     }
77 
78      public  static  void main(String[] args) {
79          int key = 85;
80          int array[] = { 8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80, 85 };
81         BlockSearch search =  new BlockSearch();
82         
83         System.out.print("线性表: ");
84         search.printAll(array);
85 
86         IndexType[] idxGroup = search.createIndex(array, array.length, 5);
87         search.printIDX(idxGroup);
88          int pos = search.blockSearch(idxGroup, idxGroup.length, array,
89                 array.length, key);
90          if (-1 == pos) {
91             System.out.format("查找key = %d失败", key);
92         }  else {
93             System.out.format("查找key = %d成功，位置为%d", key, pos);
94         }
95     }
96 
97 }