+ Prakhar Jain On Sun, Jun 24, 2012 at 2:03 PM, Prakhar Jain <[email protected]> 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: [email protected] > [email protected] > > > > On Sun, Jun 24, 2012 at 2:26 PM, adarsh kumar <[email protected]> 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 <[email protected]>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: [email protected] >>> [email protected] >>> >>> >>> >>> On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh <[email protected] >>> > 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 <[email protected]> >>>> 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 <[email protected] >>>> > >>>> > 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 [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. >>>> > >>>> > >>>> > -- >>>> > 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. >>>> >>>> -- >>>> 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. >>>> >>>> >>> -- >>> 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. >>> >> >> -- >> 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. >> > > -- > 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. > -- 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.
