# Best Algorithm for searching for an index in an array such that A[i] = i

Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log n)$ order of comparisons. The other part of question demanded to prove there exists no other algorithm which does better than this. I tried to design an adversarial argument but it didn't seem to go in the correct direction. How can one go about proving this with an adversary argument , if one exists. Other approaches to proving this are also welcome. My algorithm works as follows :

Search(A , start , end)
Find mid
if A[mid] > mid // the element with A[i] = i cannot exist in A [mid ... end]
Search (A,start, mid-1)
else if A[mid] < mid // the element with A[i] = i cannot exist in A [start... mid]
Search(A,mid+1,end)
else if(A[mid] = mid)
return A[mid];
else
return false;
end


Edit: edit contains my algorithm. Kindly forgive any typesetting errors

• Notice that if we construct a new array $B[i] = A[i]-i$ then the problem is equivalent to finding an element of the array equal to $0$ (which reduces the problem to simply proving that binary search is the most optimal for finding a specific element in an array) – cirpis Sep 10 '17 at 5:17
• @cirpis the algorithm described by you is a correct approach but this doesn't help me see why an algorithm cannot exist which uses less comparisons than binary search – Shubham Singh rawat Sep 10 '17 at 5:20
• (If you don't insert a space before punctuation marks (argument , if), the mark never gets wrapped to a line different from what it terminates.) I tried to design an adversarial argument but it didn't seem to go in the correct direction. Show what you tried! – greybeard Sep 10 '17 at 5:23
• Could you, at least, describe your algorithm? First, we should be sure that your algorithm is correct. – fade2black Sep 10 '17 at 5:24

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index.

Edit: To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will work in no less than $O(\log(n))$. The proof involves information theorethic reasoning, since storing $n$ different numbers (the indices of the array) requires each to be represented by no less than $\log(n)$ bits. Now we can see, that in order for you to output/write the solution you need $\Omega(\log(n))$ bits, and you cannot do away with less (we can apply the same reasoning to comparisons since we need to compare $\log(n)$ bits to deduce whether one number is less than the other if they are the same on all but the last bit) This means that any algorithm will need atleast $O(\log(n))$ operations to produce output.

Now, obviously, since you have produced an algorithm working in $O(\log(n))$ then the bound is sharp.

this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays?


while this is true for both unsorted and sorted arrays, it merely specifies a lower bound on the complexity of algorithms. This means that no algorithm can do better than $O(\log(n))$. It does not guarantee that there exists one though.

In an unordered array there are extra complexities that arrise, which prevent an $O(\log(n))$ solution. So we might say that the $\Omega(\log(n))$ is not sharp in this case since there does not exist an $O(\log(n))$ algorithm which could solve this problem for an unsorted array.

If we were to find a sharp lower bound for the unsorted array problem then we would need to use different assumptions and conduct a different analysis.

An important thing to realise is that this is all dependent on the underlying model of computations used. Is it assumed that comparisons take $O(1)$? How about writing a number to memory? If this is not defined then estimating complexity is tricky to say the least.

• this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays? – Shubham Singh rawat Sep 10 '17 at 5:39
• $\Omega(\log{n})$ bits are needed at least to write/output the index. – fade2black Sep 10 '17 at 6:43
• @ShubhamSinghrawat, because there are no hints in unsorted array that will help you to find element in log time. Searching in unsorted array in log time can be done non-deterministically, but not deterministically. – rus9384 Sep 10 '17 at 12:40