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 
In Python.
def research(x, seq): if not seq: return -1 if len(seq) == 1: return 0 if seq[0] == x else -1 m = len(seq) // 2 if x <= seq[m]: k = research(x, seq[m:]) return research(x, seq[:m]) if k == -1 else k + m else: k = research(x, seq[:m]) return research(x, seq[m:]) if k == -1 else k print(research(5, range(10))) # 5 print(research(20, range(10))) # -1 print(research(5, range(10)[::-1])) # 4 print(research(20, range(10)[::-1])) # -1Surely an O(2n) algorithm is also O(n), at least if I understand the definition of big-O correctly. What is more, you can make linear search take 2n time by running it twice, discarding the first result.
@JohnCowan: Your understanding of big-O notation is correct. Read the article for their definition of pessimal. Basically, it’s cheating to do things like run a calculation twice or include a useless loop that takes up time; the algorithm must make progress toward its goal at every step.
My first attempt was slow enough, but did not produce the correct result. This version seems to work better.
def research(x, seq): if not seq: return -1 if len(seq) == 1: return 0 if seq[0] == x else -1 m = len(seq) // 2 seqL, seqR = seq[:m], seq[m:] if x <= seq[m]: kR = research(x, seqR) return research(x, seqL) if kR == -1 else kR + m else: kL = research(x, seqL) if kL == -1: kR = research(x, seqR) return -1 if kR == -1 else kR + m else: return kL for i in range(-1, 5): assert research(i, range(5)) == ipublic class ReluctantSearch {
public static void main(String[] args) {
int[] input = new int[] {1, 2, 3, 4, 5, 6};
System.out.println(“Position “+research(3, input, 0, input.length-1));
System.out.println(“Position “+research(7, input, 0, input.length-1));
}
private static int research(int x, int[] input, int i, int j) {
if(i > j) return -1;
if(i == j)
if(x == input[i])
return i;
else return -1;
int m = (i+j)/2;
if(x <= input[m]) {
int k = research(x, input, (m+1), j);
if (k==-1) {
return research(x, input, i, m);
} else return k;
} else {
int k = research(x, input, i, m);
if(k==-1) {
return research(x, input, (m+1), j);
} else return k;
}
}
}
public class ReluctantSearch { public static void main(String[] args) { int[] input = new int[] {1, 2, 3, 4, 5, 6}; System.out.println("Position "+research(3, input, 0, input.length-1)); System.out.println("Position "+research(7, input, 0, input.length-1)); } private static int research(int x, int[] input, int i, int j) { if(i > j) return -1; if(i == j) if(x == input[i]) return i; else return -1; int m = (i+j)/2; if(x <= input[m]) { int k = research(x, input, (m+1), j); if (k==-1) { return research(x, input, i, m); } else return k; } else { int k = research(x, input, i, m); if(k==-1) { return research(x, input, (m+1), j); } else return k; } } }To achieve optimal pessimality, I have transformed the algorithm into non-recursive form with an explicit stack (and done what is effectively the obvious tail recursion elimination):
#include <stdio.h> #include <stdlib.h> #include <vector> #include <utility> int research(int X, int A[], int i, int j) { std::vector<std::pair<int,int> > stack; while (true) { if (i < j) { int m = (i+j)/2; if (X <= A[m]) { stack.push_back(std::make_pair(i,m)); i = m+1; } else { stack.push_back(std::make_pair(m+1,j)); j = m; } } else if (i == j && X == A[i]) { return i; // The fun is over } else if (stack.empty()) { return -1; } else { i = stack.back().first; j = stack.back().second; stack.pop_back(); } } } int main(int argc, char* argv[]) { int N = atoi(argv[1]); int X = atoi(argv[2]); int A[N]; for (int i = 0; i < N; i++) A[i] = i; int k = research(X,A,0,N-1); printf("%d\n", k); }