+ Prakhar Jain
On Sun, Jun 24, 2012 at 2:03 PM, Prakhar Jain <jprakha...@gmail.com> wrote:
> 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.
>
--
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.
