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'.