# Find minimum in rotated sorted array 2

Aug 6th, 2022 (edited)
1,166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution:
2.     def findMin(self, a: List[int]) -> int:
3.         l,r=0,len(a)-1
4.         while l<r:
5.             m=(l+r)>>1
6.             if a[m]>a[r]:#Always compare with right side that too decreasing order
7.                 l=m+1
8.             elif a[m]==a[r]:
9.                 r=r-1
10.             else:
11.                 r=m
12.         return a[l]
13.
14.
15. class Solution:
16.     def findMin(self, a: List[int]) -> int:
17.         ans=inf
18.         def bin_dfs(s,e):
19.             nonlocal ans
20.             if e-s<=1:#If array is length of 2 or less than 2
21.                 ans=min(ans,a[s],a[e])
22.                 return
23.             else:
24.                 m=s+(e-s)//2
25.                 if a[s]<=a[m]:#If left part is sorted go for right
26.                     bin_dfs(m,e)
27.                 if a[m]<=a[e]:#If right part is sorted go for left
28.                     bin_dfs(s,m)
29.         bin_dfs(0,len(a)-1)
30.         return ans
31.
32.