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

-

## 2 Answers

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

-
My goal is to try to use a divide and conquer approach to solve this problem.... –  Patric Feb 17 '13 at 9:41
Thank u for ur effort! it works when u have the case where u have 1 element equal the index, but what if I want to print all elements with equal array index? Try l = [1,2,3,3,4,6,7,8,9]...it will print only one element. –  Patric Feb 17 '13 at 18:20
Look my possible solution above... –  Patric Feb 17 '13 at 18:29
In your solution you are using stdout to collect the indices, which is fine, but is not very reusable. Also it is a bit like cheating if you want to really implement a divide and conquer algorithm ;-) The "Collect Results"-part is important, I think. –  mr- Feb 17 '13 at 20:52

I guess this would be a possible solution where i print out all possibile elements where value=index.

``````public static int IndexSearch(int []A, int l, int r) {

if (l>r)
return -1;

//Divide into subproblems
int m = (l+r)/2;

//Conquer and find solution to subproblems recursively
IndexSearch(A, l, m-1);
IndexSearch(A, m+1, r);

//Combine solutions of subproblems to the orignal solution of the problem
if (A[m]==m)
System.out.println(m);

return 1;
``````

}

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}