How could you find first occurence in Logn time using a variant of BS?

Question

I mean i guess it should be in O(n/2) i.e. O(n) time. Because one must check for every element starting from the first one till n/2 th element & for each of which one must whether A[i]==A[n/2 +i].

Please explain.

Comments

http://www.geeksforgeeks.org/find-first-and-last-positions-of-an-element-in-a-sorted-array/

Answer 1

Let for a particular index i check that condition A[i]==A[i+1] or not..
 if it is true then (check A[2i]==A[n/2+1] or not )
else select i+1 for same purpose..

let size of array is 100 and A[0]=A[2]=A[4]!=A[8]
then dont check for A[2] as well as A[4]..
this ll reduce no of comparison to logn..

Comments

Yeah !
Thanks.