Create a graph showing expected cost versus the probability of an unsuccessful search when performing sequential search (see Section 9.1). What can you say qualitatively about the rate of increase in...

Create a graph showing expected cost versus the probability of an unsuccessful search when performing sequential search (see Section 9.1). What can you say qualitatively about the rate of increase in expected cost as the probability of unsuccessful search grows?

Modify the binary search routine of Section 3.5 to implement interpolation search. Assume that keys are in the range 1 to 10,000, and that all key values within the range are equally likely to occur.