Advertisement
Iam_Sandeep

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.        
Advertisement
RAW Paste Data Copied
Advertisement