Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def binary_search(sorted_list, value):
- left = 0
- right = len(sorted_list) - 1
- while left <= right:
- mid = right + left // 2
- if sorted_list[mid] > value:
- right = mid - 1
- elif sorted_list[mid] < value:
- left = mid +1
- else:
- # found value but is it the first occurence
- chk = mid
- while sorted_list[chk] == value:
- mid = chk
- if chk > 0:
- chk -= 1
- else:
- return mid
- return mid
- # loop ends return `False`
- return -1
- list_of_numbers = [1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
- print("list of numbers is {}".format(list_of_numbers))
- search_number = 4
- print("Number to find is {}".format(search_number))
- item_at = binary_search(list_of_numbers, search_number)
- # Display result of search
- if item_at < 0:
- print("{} is not in the list of numbers".format(search_number))
- else:
- 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