There is a family of tree search algorithms that compare ordered keys with one another to see if they are greater or less; the simplest one uses a binary search tree; and there is a family of tree data structures known as tries (what is this trie thing ?) that don't compare keys with one another except at the end. |
There is a family of tree search algorithms that compare ordered keys with one another to see if they are greater or less; the simplest one uses a binary search tree; and there is a family of tree data structures known as tries that don't require a key compare until the end of the search. |
The simplest search algorithm is linear search. It has O(n) running time, but can operate on a list containing the elements of the set.
A more sophisticated search algorithm is binary search. It runs in O(log(n)). This is significantly better than linear search for large lists of data, but it requires that the list be sorted before searching (see sort algorithm) and also be random access.
[Interpolation search]? is better than binary search for large sorted lists.
There is a family of tree search algorithms that compare ordered keys with one another to see if they are greater or less; the simplest one uses a binary search tree; and there is a family of tree data structures known as tries that don't require a key compare until the end of the search.
Hash tables are also used for search; they are the method of choice in most circumstances today.
There are also string search algorithms, which are related but different.