Lookup - lookup of sequential table and ordered table

This article mainly talks about the static search of sequential table search and ordered table search

1. Sequential storage structure

Typedef struct {

ElemType*elem;( Base address of data element storage space ,0 Unit No. is left blank )

int length;( Table length ) 

}SSTable;

1.1  Sequence table lookup

The search of sequence table is applicable to the record table stored in sequence and linked list . Compare with the given value one by one from either end of the table , If equal , Then the search is successful . The return value is the position sequence number of the record in the table ; If beyond the limit , The search fails . Return value is zero . Suitable for sequential storage and linked list storage .

1.1.1  Sequential search of CIS storage

• Find from tail

Int Search-Seq(SSTableST,keyTypekey){

ST.elem[0].key=key;

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);

return i; 

} Search-seq 

• 
  
  Look in the head

int Search_seq(SSTable ST,keytype key)

int i= 1;

{

while(i <= ST.length &&ST.elem[i].key!= key)

i++;

if(i>ST.length) return FALSE; // Did not find

else return i; // eureka

}

• Searching from the head is less efficient than searching from the tail , It is suggested to use the tail search method

1.1.2  Sequential search of chain storage

status getelement(link head,keytype key){

(for(p=head;p!=NULL&&p->key!=key;p=p->next);

return p;

}

1.2 Lookup of ordered table

1.2.1  Binary search

Binary search (Binary Search) The process is :  First, calculate the middle position of the checked table ;  Then compare the keyword recorded in the middle position with the given value : If it is equal, the search is successful ; If the keyword recorded in the middle position is less than the given value ,  Then continue to search from the second half of the table next time ;  If the keyword recorded in the middle position is greater than the given value ,  Next time, continue to search the first half of the table .

for example ： lookup 21 Need to compare 3 Time .

• 
  
  Algorithm

Int Search-Bin(SSTable ST,keyType key) { 

low = 1; high = ST.length; While( low<=high ) { 

mid =(low +high)/2;

if EQ(key,ST.elemmid].key) return mid;

else if LTkey,ST.elem[mid].key) high= mid-1; else low =mid +1 ;

}

return 0;

}

The process of half search can be represented by the following decision tree :

As can be seen from the figure below , lookup 21 The process just goes through a path from the root  21  To the node 4 The path of , The number of keywords compared with a given keyword is the number of nodes or nodes on the path 4 The number of layers on the decision tree . Other nodes are similar . therefore , Half search the number of keywords to compare when the search is successful does not exceed the depth of the tree , And have n The depth of the decision tree of nodes is  [log₂n] +1, Therefore, the maximum number of keywords to compare with the given value when the half search is successful is  [log₂n] +1.