def find_min_in_valley(l): \"\"\" You are given a non-empty list such that there

Question

def find_min_in_valley(l):

""" You are given a non-empty list such that there is a unique index 0 <= i < len(l) where the sublist l [0:i+1] is strictly decreasing and the sublist l [i:len(l)] is strictly increasing. Return this index i. Your algorithm should run in O(log n) time.

>>> find_min_in_valley([3, 2, 1, 0, -1, 1, 2]) 4

>>> find_min_in_valley([3, 2, 0, 2, 4]) 2

>>> find_min_in_valley([0]) 0

>>> find_min_in_valley([1,2,3]) 0

>>> find_min_in_valley([7,5,1]) 2 """

pass

Please answer in python, I will rate!

Explanation / Answer

''' We can solve this by using modified version of binary search. Time complexity of binary search in worst case is O(LogN) if size of list is N How this algorithm is working? Important Point: Since array is sorted and rotated so there will be one element which will be smaller than its neighbours. Using this technique , see the steps for modified version of binary search to solve your problem list = [3, 4, 5, 1, 2] We want to search element 1 left=0, right=4 --First handle base cases --if (left == right) ----return left --Run loop --while(left when you have reached termination condition -----------return left ----(1) find the middle of the indexes: --------mid=(left+right)//2 ----(2)if (mid l[mid + 1]): => This can be happen at one place only for rotation return mid + 1 ----(3)elif(left

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.