## Reluctant Search

### April 3, 2015

It is simple to translate the article’s pseudocode to Scheme:

```(define (research x xs i j)     (if (> i j)         -1         (if (= i j)             (if (= x (vector-ref xs i))                 i                 -1)             (let ((m (quotient (+ i j) 2)))                 (if (<= x (vector-ref xs m))                     (let ((k (research x xs (+ m 1) j)))                         (if (= k -1)                             (research x xs i m)                             k)))                     (let ((k (research x xs i m)))                         (if (= k -1)                             (research x xs (+ m 1) j)                             k)))))))```

Here are two examples:

```> (research 3 '#(1 2 3 5 6) 0 4) 2 > (research 4 '#(1 2 3 5 6) 0 4) -1```

You can run the program at http://ideone.com/IA1vZc. Happy belated April Fools’ Day!

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