@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again
below with an update
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||mid==0)
{
if(mid==0&&A[0]!=0)
return 0;
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 Sat, Dec 4, 2010 at 8:08 PM, Ashim Kapoor <ashimkap...@gmail.com> wrote:
> yaar I can use simple O(n) sweep to find out who all are equal, I think it
> can't be less than this
>
>
> On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun <abioy....@gmail.com> wrote:
>
>> 2010/12/4 ankit sablok <ankit4...@gmail.com>:
>> > as all the elements are sorted in the array make a min heap of the
>> > array elements and as min heap is a tree of keys querying a min heap
>> > or a binary search tree requires operations with time equal to the
>> > height of the tree which is log(n) hence time for querying a min heap
>> I think you might be use a log(n) time to find out a element whose
>> value is equal to some certain index, so the complexity could be
>> n*log(n)?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
