Advertisement
Iam_Sandeep

162.Find any peak element in given series

Jul 3rd, 2022
1,303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.84 KB | None | 0 0
  1. Method 1:
  2. class Solution:
  3.     def findPeakElement(self, a: List[int]) -> int:
  4.         n=len(a)
  5.         l,r=0,n-1
  6.         while l<r:
  7.             m=(l+r)>>1#Find mid
  8.             '''
  9.            You found increasing part from mid right side. So 100% sure that peak will be rightside.
  10.            It is not 100% sure that peak will be left. So you shift l to m+1
  11.            '''
  12.             if a[m]<a[m+1]:
  13.                 l=m+1
  14.             '''
  15.            You found decreasing part from mid to left side. So 100% sure that peak will be left side.
  16.            It is not 100% sure peak will be right. So you shift r to m. Since even r is eligible for being Peak(VVimp)
  17.            '''
  18.             else:
  19.                 r=m
  20.             '''
  21.            To avoid infinite loop we removed l<=r and made it to l<r
  22.            '''
  23.         return l
  24.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement