search - Searching an array with monotonic sequences of values -


i have large array values go monotonically , down (no ties) in long sub-sequences (such sequences can number , of arbitrarily large size, , of course > 2 terms).

example in small scale:

1 2 3 4 5 9 7 4 3 -2 -5 -7 3 5 34 56 67 78 89 90 8 6 2 -4 -5 ...

and on.

i interested in finding any (just 1, not all) of values ending increasing sequence , right new decreasing sequence starts.

what best way , complexity ?

(my intuitive idea done binary search, guessing o(logn), not sure if might right)

you cant apply binary search here because given sequence not sorted. can in o(n) searching first element next element less element. in above example 9 answer


Comments

Post a Comment

Popular posts from this blog

jquery - How do you format the date used in the popover widget title of FullCalendar? -

Image
in fullcalendar, how format date used in popover widget title when clicking '+n more'? code: <div class="fc-popover fc-more-popover"> <div class="fc-header fc-widget-header"> <span class="fc-close fc-icon fc-icon-x"></span> <span class="fc-title">tuesday, april 7</span> ... </div> ... </div> you use daypopoverformat that. determines date format of title of popover created eventlimitclick option. must date formatting string. default value "dddd, mmmm d" english , "ll" other languages.
Read more

asp.net mvc - SSO between MVCForum and Umbraco7 -

i need integrate sso between mvcforum (forum of company) , umbraco7 (manages cms company). however struggling shared authentication work. tried several ways suggested on other threads still not running expected. here did: 1. in mvcforum (forum.mywebsite.com) 1.1. machine key in web.xml: <machinekey validationkey="the same key umbraco7" decryptionkey="the same key umbraco7" validation="sha1" decryption="aes" /> 1.2. authenticate forms in web.xml <forms name="my-sso-auth" protection="all" path="/" timeout="43200" domain="forum.mywebsite.com" loginurl="/members/logon" enablecrossappredirects="true" /> 2. in umbraco7 (news.mywebsite.com) 2.1. machine key in web.xml: <machinekey validationkey="the same key mvcforum" decryptionkey="the same key mvcforum" validation="sha1" decryption="aes" /> 2.2. a...
Read more

Python Tkinter keyboard using bind -

i have problem using bind option can click button in keyboard, , call function once key pressed. tried taking other codes have similar purpose , saw i'm doing pretty same, though still have problem must've missed. thankful if me this. here's code: # -*- coding: utf-8 -*- #imports tkinter import * pil import imagetk, image import time import tkmessagebox #===========================================================================================================================================# #tkinter class class app(frame): def __init__(self, master=none): frame.__init__(self, master) self.pack() #===========================================================================================================================================# #game pieces classes class board: def __init__(self, rows = 7, columns = 6, picture_height = none, picture_width = none): self.rows = rows self.columns = columns self.picture ...
Read more