Search code examples
recurrencedivide-and-conquer

Divide and conquer: IndexSearch


i solved the following task by myself:

Give an algorithm to find an index i such that 1 <= i <= n and A[i] = i provide such an index exists. If there are any such indexes, algorithm can return any of them.

I used the divide and conquer approach and as result i get:

public static int IndexSearch(int []A, int l, int r) {
  if (l>r)
     return -1;
  int m = (l+r)/2;  
  IndexSearch(A, l, m-1); 
  IndexSearch(A, m+1, r);
  if (A[m]==m)
     return m;
  else
     return -1;
}

First wanted to ask if it is correct? I guess yes....

What is the recursion T(n) in this case?

I presume:

2T(n/2) + O(1) ----> is it right? can one explain me in detailed way how to solve the recurrence applying the Master Theorem ?

a=2 b=2 f(n)=1 n^logba = n ---> n vs 1 so we have CASE 1 which leads to O(n) -> ???? right?


Solution

  • It most certainly is not correct.

    Since you ignore the return-values of your recursive calls, your program really only checks if A[m] == m in your very first call and returns -1 if that is not the case.

    The "obvious" solution would be something like:

    public static int IndexSearch(int []A, int l, int r) {
      for i in range(1, length(A))
        if (A[i] == i)
          return i
      return -1
    }
    

    Also it is a very clear solution, so maybe that's to be preferred over a more sophisticated one.

    I am sorry, I cannot help you with your other questions.

    EDIT: This should work. It is written in Python, but it should be easy enough to understand. The point about divide and conquer is to reduce the problem to a point where the solution is obvious. In our case, that would be the list with only one element. The only difficulty here is passing back the return values.

    def index(l, a, b):
        if a == b: #The basecase, we consider a list with only one element
            if l[a] == a:
                return a
            else: return -1
    
        #Here we actually break up
        m = (a+b)/2
    
        i1 = index(l, a, m)
        if i1 != -1:
            return i1
    
        i2 = index(l, m+1, b)
        if i2 != -1:
            return i2
    
        return -1
    

    Here is an example output:

    l = [1,2,3,3,5,6,7,8,9]
    print index(l, 0, len(l)-1)
    
    Output: 3
    

    Hope that helps.

    EDIT: Finding all occurences actually leads to a much nicer solution:

    def index(l, a, b):     
        if a == b:
            if l[a] == a:
                return [a]
            else:
                return []
    
        m = (a+b)/2
        return index(l, a, m) + index(l, m+1, b)
    

    Which has as ouput:

    l = [1,2,3,3,5,6,7,8,8]
    print "Found " , index(l, 0, len(l)-1), " in " , l
    
    Found  [3, 8]  in  [1, 2, 3, 3, 5, 6, 7, 8, 8]
    

    and

    l = range(0,5)
    print "Found " , index(l, 0, len(l)-1), " in " , l
    
    Found  [0, 1, 2, 3, 4]  in  [0, 1, 2, 3, 4]
    

    I think that makes for a nice, pure solution ;-)