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:
- return mid # found exact match
- # search value lies between current 2 items
- elif sorted_list[mid] < value and sorted_list[mid + 1] > value:
- if value - sorted_list[mid] == sorted_list[mid +1] - value:
- return mid
- elif value - sorted_list[mid] < sorted_list[mid +1] - value:
- return mid
- else:
- return mid + 1
- # keep looking
- elif sorted_list[mid] > value:
- right = mid - 1 # too high
- elif sorted_list[mid] < value:
- left = mid +1 # too low
- # loop ends return `False`
- return False
- list_of_numbers = [1, 2, 3, 5, 6, 7]
- print("list of numbers is {}".format(list_of_numbers))
- search_number = 3.5
- print("Number to find is {}".format(search_number))
- # 1st check first and last numbers in the list
- last = len(list_of_numbers) - 1
- # is number to find lower than 1st number in the sorted list
- if list_of_numbers[0] > search_number:
- print("{} is not in the list".format(search_number))
- # is number to find higher than last number in sorted list
- elif list_of_numbers[last] < search_number:
- print("Largest number in list is {}".format(list_of_numbers[last]))
- else :
- # call binary search
- item_at = binary_search(list_of_numbers, search_number)
- # Display result of search
- if list_of_numbers[item_at] == search_number:
- # number has been found
- print("{} is in the list at posn {}".format(search_number, item_at))
- else:
- # only closest number found
- print("Closest number is {} at posn {}".format(list_of_numbers[item_at], item_at))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement