@sourabh notice the definition of peak in the link given earlier. it says that peak element would not be smaller than its neighbours implying that it can be equal to them and still qualify for a peak. hence the given algo would work in the sample given by you or any other sample.
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. > -- Aditya Gupta B.Tech III yr CSE IITR -- 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.
