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: }