R@M3$H.NBlog

Word Lookup in a Dictionary

03 February, 2014 - 2 min read

What method would you use to look up a word in a dictionary ?

This is a classic binary search algorithm:

   1: // Assume dict is a sorted dictionary.

   2: // Call with p = 0, q = dict_size - 1;

   3: bool search(char** dict, char* s, int p, int q) {

   4:   if (p > q) return false;

   5:   int mid = (p + q) / 2;

   6:   int c = strcmp(dict[mid], s);

   7:   if (c < 0) return search(dict, s, p, mid - 1);

   8:   if (c > 0) return search(dict, s, mid + 1, q);

   9:   return true;

  10: }