The idea behind this O(log n) Divide & conquer algorithm is they assumed
that element before the first element and after the last element is
-infinite. So, they can they always pick the locally rising element ;since,
even if the array continues to increase in that half, the last element can
be the peak element. So, the peak element is always there in the array even
if it is sorted in any order.
--
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 2:26 PM, adarsh kumar <algog...@gmail.com> wrote:
> ahh yes, as prakhar says, if the array is bitonic, my approach will work
> for O(log n).
>
>
> On Sun, Jun 24, 2012 at 1:57 AM, Prakhar Jain <jprakha...@gmail.com>wrote:
>
>> 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.
>>
>
> --
> 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.
