数据结构各种算法原代码及图形示例

				算法 8.3
				int Search_Idx ( SSTable ST,  indexTable ID,  KeyType kval ) 
				{
				  // 在顺序表ST中分块查找其关键字等于给定值kval的数据元素，ID为索引表。
				  // 若找到，则返回该数据元素在ST中的位置，否则返回0
				   low = 0;  high = ID.length-1;  found = FALSE;
				   if (kval>ID.elem[high].key) return 0;   // 给定值kval大于查找表中所有关键字
				   while ( low 				     mid = (low+high)/2;
				     if ( kval < ID.elem[mid].key )  high = mid - 1;
				     else if ( kval > ID.elem[mid].key )  low = mid +1;
				        else {  found = TRUE;  low = mid;  }
				    }//while
				   s = ID.elem[low].stadr; // 经索引表查找后，下一步的查找范围定位在第low块
				   if ( low < ID.length-1 )  t = ID.elem[low +1].stadr-1; 
				   else t = ST.length;    
				        // s和t为在ST表进行查找的下界和上界，若不是最后一块，则上界为“下一块的起始位置之前”
				   if ( ST.elem[t].key== kval )  return t;
				   else {              // 在ST.elem[s] 至ST.elem[t-1]的区间内进行顺序查找
				     ST.elem[0] = ST.elem[t]; // 暂存ST.elem[t]
				     ST.elem[t].key = kval;   // 设置监视哨
				     for ( k=s;  ST.elem[k].key !=kval;  k++ ) ;
				     ST.elem[t] = ST.elem[0]; // 恢复暂存值
				     if ( k != t ) return k;
				     else return 0;
				   } // else
				} // Search_Idx