SHARE
TWEET

Untitled

a guest Sep 19th, 2019 102 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def local_maxima(A, ind_left, ind_right):
  2.     # check the edge cases
  3.     if ind_left == 0 and A[ind_left] >= A[ind_left + 1]:
  4.         return ind_left
  5.     elif ind_right == len(A) - 1 and A[ind_right - 1] <= A[ind_right]:
  6.         return ind_right
  7.  
  8.     ind_mid = (ind_left + ind_right) // 2
  9.  
  10.     # case 0:
  11.     if A[ind_mid - 1] <= A[ind_mid] >= A[ind_mid + 1]:
  12.         return ind_mid
  13.  
  14.     # case: 1
  15.     elif A[ind_mid] < A[ind_mid + 1]:
  16.         return local_maxima(A, ind_mid + 1, ind_right)
  17.  
  18.     # case: 2
  19.     else:
  20.         return local_maxima(A, ind_left, ind_mid - 1)
  21.  
  22.  
  23.  
  24. def main():
  25.     arr = [1, 10, 9, 8, 7]
  26.     assert len(arr) >= 2, "please use an array with length >= 3"
  27.  
  28.     # Note that the below sorted check is done for validity of question
  29.     # and this logic is not actually part of the solution
  30.     is_ascending = True
  31.     is_descending = True
  32.     for i in range(len(arr) - 1):
  33.         if arr[i] > arr[i + 1]:
  34.             is_ascending = False
  35.         elif arr[i] < arr[i + 1]:
  36.             is_descending = False
  37.     is_sorted = is_ascending or is_descending
  38.     assert is_sorted is False, "please use an unsorted array"
  39.  
  40.     print(local_maxima(arr, 0, len(arr) - 1))
  41.  
  42.  
  43. if __name__ == "__main__":
  44.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top