Please solve in python 3 Download the file findpeak.py and implement the functio
ID: 3809676 • Letter: P
Question
Please solve in python 3
Download the file findpeak.py and implement the function find peak as described in the file. Your implementation should solve this problem in olog(n)) time where n is the size of the list (hint: divide and conquer, i e., what underlies merge sort and many other recursive algorithms). Trivial solutions that run in 2(n) time will not receive any marks. Submit your solution as a single uncompressed file findpeak.py. Remember to include comments! Warning: if your code performs a list slice (something like l k1 or l k:1) then it is probably taking 20n) time! In particular, list slice unfortunately makes a full copy of the sliced portion of the list.Explanation / Answer
def find_peak(hill):
st1 = 0
ed1 = len(hill)-1
st = st1
ed = ed1
ans = 0
while True:
if(ed==st):
ans=ed
break
if(ed-st==1):
if(hill[ed]>hill[st]):
ans = ed
else:
ans = st
break
md = (ed-st)/2 + st;
if(hill[md]>hill[md-1]):
st = md
else:
ed = md
return ans
q = [1,2,3,4,3,1]
print(find_peak(q))
q = [1,3,6,7,4,1]
print(find_peak(q))
q = [4]
print(find_peak(q))
q = [1,2,3]
print(find_peak(q))
q = [9,4]
print(find_peak(q))
q = [1,8,6,2]
print(find_peak(q))