Advertisement
farrismp

binary search first occurance

May 10th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.06 KB | None | 0 0
  1. def binary_search(sorted_list, value):
  2. left = 0
  3. right = len(sorted_list) - 1
  4. while left <= right:
  5. mid = right + left // 2
  6. if sorted_list[mid] > value:
  7. right = mid - 1
  8. elif sorted_list[mid] < value:
  9. left = mid +1
  10. else:
  11. # found value but is it the first occurence
  12. chk = mid
  13. while sorted_list[chk] == value:
  14. mid = chk
  15. if chk > 0:
  16. chk -= 1
  17. else:
  18. return mid
  19. return mid
  20. # loop ends return `False`
  21. return -1
  22.  
  23. list_of_numbers = [1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
  24. print("list of numbers is {}".format(list_of_numbers))
  25.  
  26. search_number = 4
  27. print("Number to find is {}".format(search_number))
  28.  
  29. item_at = binary_search(list_of_numbers, search_number)
  30. # Display result of search
  31. if item_at < 0:
  32. print("{} is not in the list of numbers".format(search_number))
  33. else:
  34. print("The first time {} is in the list is at posn {}".format(search_number, item_at))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement