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[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])) # -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[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)) == 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[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);
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: