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