## 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.

Pages: 1 2

### 7 Responses to “Reluctant Search”

1. Paul said

In Python.

```def research(x, seq):
if not seq:
return -1
if len(seq) == 1:
return 0 if seq == 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])) # -1
```
2. John Cowan said

Surely 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.

3. programmingpraxis said

@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.

4. Paul said

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 == 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)) == i
```
5. Krishnan R said

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;
}
}
}

6. Krishnan R said
```
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;
}
}
}

```
7. matthew said

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);
int X = atoi(argv);
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);
}
```