Reluctant Search
April 3, 2015
Wednesday was April Fools’ Day, and I was feeling frisky, so I implemented the reluctant search algorithm from Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi. Their algorithm takes time O(2n), which is worse than the naive brute force O(n), to find the index of a target x in a sorted array. We looked at a different algorithm that paper in a previous exercise. I’ll leave it to you to fetch the paper and enjoy the sincerity of the authors’ pessimality.
Your task is to implement the reluctant search algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 