算法 8.3
int Search_Idx ( SSTable ST,  indexTable ID,  KeyType kval ) 
{
  // 在順序表ST中分塊查找其關(guān)鍵字等于給定值kval的數(shù)據(jù)元素，ID為索引表。
  // 若找到，則返回該數(shù)據(jù)元素在ST中的位置，否則返回0
   low = 0;  high = ID.length-1;  found = FALSE;
   if (kval>ID.elem[high].key) return 0;   // 給定值kval大于查找表中所有關(guān)鍵字
   while ( low <=high && !found ) { // 折半查找索引表，確定記錄查找區(qū)間
     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; // 經(jīng)索引表查找后，下一步的查找范圍定位在第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]的區(qū)間內(nèi)進行順序查找
     ST.elem[0] = ST.elem[t]; // 暫存ST.elem[t]
     ST.elem[t].key = kval;   // 設(shè)置監(jiān)視哨
     for ( k=s;  ST.elem[k].key !=kval;  k++ ) ;
     ST.elem[t] = ST.elem[0]; // 恢復(fù)暫存值
     if ( k != t ) return k;
     else return 0;
   } // else
} // Search_Idx