I think it can't be done in O(log n) as per given problem constraints.
It can be done in O(log n) if additional information that "array is
bitonic" is given.
--
Prakhar Jain
IIIT Allahabad
B.Tech IT 3rd Year
Mob no: +91 9454992196
E-mail: rit2009...@iiita.ac.in
jprakha...@gmail.com
On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh <singhsourab...@gmail.com>wrote:
> @adarsh kumar
>
> are u sure it's worst case will be O (log n) ??
> i think iff array is fully sorted O(n) will be required to say "NO
> such element present"
>
> On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar <algog...@gmail.com> wrote:
> > This is a variation of binary search, the difference being that we have
> to
> > search for an element that is greater than its immediate left one and
> lesser
> > than its immediate right one. Just implement binary search with these
> > additional constraints, thereby giving O(log n).
> > In case of any difficulty/error, let me know.
> >
> > On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared <hmonfa...@gmail.com>
> > wrote:
> >>
> >> Given an array of integers find a peak element of array in log(n) time.
> >> for example if A={3,4,6,5,10} then peak element is 6 ( 6>5 & 6>4 ).
> >>
> >> Regards.
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To view this discussion on the web visit
> >> https://groups.google.com/d/msg/algogeeks/-/AQI6ahWgyOIJ.
> >> To post to this group, send email to algogeeks@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.
> >
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
