Problem
(a) Write a program to do interpolation search and verify its correctness (especially termination). See the references at the end of the chapter for suggestions and program analysis.
(b) Include your function as another option in the testing program and compare its performance with the other methods.