If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.
Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
FIND_EQUAL(A,start,end)
1.Go to the middle element
2.If A[mid]==mid)
return mid+1;
if(A[mid]>mid)
then FIND_EQUAL(A,start,mid-1)
else
FIND_EQUAL(A,mid+1,end)
Runs in O(lgn)
On Sun, Dec 5, 2010 at 12:20 PM, jai gupta <[email protected]> wrote:
> Any algorithm must in worst case lead to O(n) if the elements are not
> unique. Take the case:
> 1 2 3 4 5 6
> as all the elements satisfy the condition of of key==index . we must go
> someway to each element.
> Hence O(n).
>
> This may be somehow made less if the element are given to be unique by
> using heap.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
