recurrence - Divide and conquer: IndexSearch -

recurrence - Divide and conquer: IndexSearch -

i solved next task myself:

give algorithm find index such 1 <= <= n , a[i] = provide such index exists. if there such indexes, algorithm can homecoming of them.

i used split , conquer approach , result get:

public static int indexsearch(int []a, int l, int r) { if (l>r) homecoming -1; int m = (l+r)/2; indexsearch(a, l, m-1); indexsearch(a, m+1, r); if (a[m]==m) homecoming m; else homecoming -1; }

first wanted inquire if correct? guess yes....

what recursion t(n) in case?

i presume:

2t(n/2) + o(1) ----> right? can 1 explain me in detailed way how solve recurrence applying master theorem ?

a=2 b=2 f(n)=1 n^logba = n ---> n vs 1 have case 1 leads o(n) -> ???? right?

it not correct.

since ignore return-values of recursive calls, programme checks if a[m] == m in first phone call , returns -1 if not case.

the "obvious" solution like:

public static int indexsearch(int []a, int l, int r) { in range(1, length(a)) if (a[i] == i) homecoming homecoming -1 }

also clear solution, maybe that's preferred on more sophisticated one.

i sorry, cannot help other questions.

edit: should work. written in python, should easy plenty understand. point split , conquer cut down problem point solution obvious. in our case, list 1 element. difficulty here passing homecoming values.

def index(l, a, b): if == b: #the basecase, consider list 1 element if l[a] == a: homecoming else: homecoming -1 #here break m = (a+b)/2 i1 = index(l, a, m) if i1 != -1: homecoming i1 i2 = index(l, m+1, b) if i2 != -1: homecoming i2 homecoming -1

here illustration output:

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

hope helps.

edit: finding occurences leads much nicer solution:

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

which has 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 makes nice, pure solution ;-)

recurrence divide-and-conquer