Given a sorted list of distinct integers A1 TripleDot n you

Given a sorted list of distinct integers A[1, TripleDot, n], you want to find out whether there is an index i for which A[i] = i. Give a divide-and-conquer algorithm that runs in time Theta (log n).

Solution

This is an algorithm to find index i such that 1 <= i <= n and A[i] = i provide such an index exists

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

Just small explanation how divide and conqure work like binary search:-

Recurrence for normal binary search is T2(n) = T2(n/2)+1.

This is accounts for one comparison (on an element which partitions the n-element list of sorted keys into two n/2 -element sets) and recursive call on the appropriate partition.

For ternary search we make two comparisons on elements which partition the list into three sections with roughly n/3 elements and recurse on the appropriate partition.

The recurrence for the number of comparisons made by this ternary search is: T3(n) = T3(n/3) + 2.

However, just as for binary search after theorem applies. We conclude that T3(n) (log(n)).