Implement a binary search and the quadratic binary search of Section 9.1.

Run your implementations over a large range of problem sizes, timing the results for each algorithm. Graph and compare these timing results.

Transcribed Image Text:

The location of a particular key within the key range is translated into the expected position for the corresponding record in the table, and this position is checked first. As with binary search, the value of the key found eliminates all records either above or below that position. The actual value of the key found can then be used to compute a new position within the remaining range of the table. The next check is made based on the new computation. This proceeds until either the desired record is found, or the table is narrowed until no records are left. A variation on dictionary search is known as Quadratic Binary Search (QBS), and we will analyze this in detail because its analysis is easier than that of the general dictionary search. QBS will first compute p and then examine L[[pn]]. If K L[[pn]] we will step forward by n until we reach a value in L that is greater than K. We are now within n positions of K. Assume (for now) that it takes a constant number of comparisons to bracket K within a sublist of size n. We then take this sublist and repeat the process recursively. What is the cost for QBS? Note that = n/2, and we will be repeatedly taking square roots of the current sublist size until we find the item we are looking for. Because n = 2logn and we can cut log n in half only log log n times, the cost is (log log n) if the number of probes on jump search is constant. The number of comparisons needed is i=1 iP (need exactly i probes)