Home  Back Topics CD Orders  INDEX 
Binary search

If the data is sorted then a fast search which can be used is a binary search.

This involves looking at the 'middle' record. If the required record is before this one, then discard the second half of the file; if it is after this one, then discard the first half of the file. Repeat the process, discarding half the file each time, until the required record is found.

Pseudocode:

Assume the data keys are stored in an array Key[1..n] and we are searching for the data whose key is WantedKey

first := 1;
last := n;
repeat
  m := (first+last) div 2;
  if WantedKey < Key[m] then
    last := m-1
  else  
    first := m+1;
until Key[m] = WantedKey;

Note that this algorithm assumes that the data key is not missing. A better algorithm would be:

first := 1;
last := n;
found := false
repeat
  m := (first+last) div 2;
  if WantedKey = Key[m] then found := true;
  if WantedKey < Key[m] then
    last := m-1
  else  
    first := m+1;
until found or (last < first);

Note that 'until found' is short for 'until found = true'.