Advertisement
MaxObznyi

Leftmost occurrence

Feb 17th, 2021
654
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.55 KB | None | 0 0
  1. #find if the element is in the list
  2. #list ISN'T sorted
  3.  
  4. n = int(input())
  5. a = list(map(int, input().split()))
  6. x = int(input())
  7.  
  8. a.sort()
  9.  
  10. #we consider elements in positions [l, r) -- a[l], a[l + 1], ..., a[r - 1].
  11.  
  12. l = -1
  13. r = n
  14. while l < r - 1: #there is more than one element
  15.     m = (l + r) // 2 #look at the value in the middle
  16.     if a[m] < x:
  17.         l = m
  18.     else:
  19.         r = m
  20. if r < n and a[r] == x: #if r ==n than there are no elements equal to x
  21.     print('The leftmost occurrence is', r)
  22. else:
  23.     print('There is no such element')
  24.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement