If you know you are going to need to search for an item in a set, you will need to think carefully about what type of data structure you will use for that set. At school level, the only searches that get mentioned are for sorted and unsorted arrays. However, these are not the only data types that are useful for searching.
Start at the beginning of the list and check every element of the list. Duh. Very slow (order O(n)) but works on an unsorted list.
This is used for searching in a sorted array. Test the middle element of the array. If it is too big, repeat the process in the left half of the array, and the right half if it's too small. In this way, the amount of space that needs to be searched is halved every time, so the time is O(log n).
Searching a hash table is easy and extremely fast: Just find the hash value for the item you're looking for, then go to that index and start searching the array until you find what you're looking for or you hit a blank spot. The order is pretty close to O(1), depending on how full your hash table is.
Searching a binary tree is just as easy as searching a hash table, but it is usually slower (especially if the tree is badly unbalanced). Just start at the root, then go down the left subtree if the root is too big and the right subtree if it is too small. Repeat until you find what you want or the subtree you want isn't there. The running time is O(log n) on average and O(n) in the worst case.
Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).