Review of Searching
Linear SearchLet us say that we have an unsorted list of zip codes stored in an array. How long will it take for us to see if a particular zip code is on the list? If we have n zip codes in the array, finding a zip code using a linear search method (for which we start at the zeroth element and look for the item one by one), will on average take O(n/2) if it is present and O(n) if it is not. Of course, we could get lucky and find it on the first try. So the best case would be O(1) while the worst case would be O(n). The average case, if the element is present, would be O(n/2) which is equal to O(n). Can we do better?
Binary SearchIf the zip codes we want to search are already sorted, we can use a binary search method to speed up our search. In this case, our worst-case search time (which is guaranteed if the element we are seeking is not part of the list) will be O( log2 (n) ). This is considerably better than the linear search but it assumes that the original list is sorted. Even if that is the case, can we do better?
Binary Tree SearchWhat if we store the zip codes in a binary tree? In the worst case scenario, each node in the tree will only have one child (i.e. an unbalanced tree). For this case, for n zip codes (each represented by one node in the tree), the height of the tree will be n-1. If we are looking for an element that is not present in the tree, our search time will be O(n). If the binary tree is complete (each node has 2 children until we run out of nodes), recall that the height of such a tree will be:
Min height of a binary tree = Ceiling ( Log2( n + 1) - 1 )
For large values of n, this height is approximatley Log2(n). Thus, for such a tree, our search efficiency will be O (log n). So the best case for searching a binary tree is the same as for a binary search. Meanwhile, the worst case is O(n). Can we do better?
Review of Efficiencies of Search AlgorithmsAll the data structures we have reviewed in this Unit result in average search times ranging from O(n) to O(log n). Is it possible, however, to build a data structure to store our zip codes so that we can search them in O(k) time? It is possible if we use a hashing scheme, which is our next (and most important) topic.
Quiz on Searching
In this quiz, you will be asked questions regarding the two searching methods previously talked about.
1 pointDoes Linear Search go through each element one by one?
1 pointIs Linear Search fast or slow (in an average amount of data)?
1 pointWhat size of data is Linear Search best at searching through?
1 pointWhat searching method plays "Hot and Cold" with the data set?
1 pointWhat searching method is faster with a large amount of data?