Advertisement
farrismp

Binary search for closest

May 10th, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.83 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. return mid # found exact match
  8. # search value lies between current 2 items
  9. elif sorted_list[mid] < value and sorted_list[mid + 1] > value:
  10. if value - sorted_list[mid] == sorted_list[mid +1] - value:
  11. return mid
  12. elif value - sorted_list[mid] < sorted_list[mid +1] - value:
  13. return mid
  14. else:
  15. return mid + 1
  16. # keep looking
  17. elif sorted_list[mid] > value:
  18. right = mid - 1 # too high
  19. elif sorted_list[mid] < value:
  20. left = mid +1 # too low
  21. # loop ends return `False`
  22. return False
  23.  
  24. list_of_numbers = [1, 2, 3, 5, 6, 7]
  25. print("list of numbers is {}".format(list_of_numbers))
  26.  
  27. search_number = 3.5
  28. print("Number to find is {}".format(search_number))
  29.  
  30. # 1st check first and last numbers in the list
  31. last = len(list_of_numbers) - 1
  32. # is number to find lower than 1st number in the sorted list
  33. if list_of_numbers[0] > search_number:
  34. print("{} is not in the list".format(search_number))
  35. # is number to find higher than last number in sorted list
  36. elif list_of_numbers[last] < search_number:
  37. print("Largest number in list is {}".format(list_of_numbers[last]))
  38. else :
  39. # call binary search
  40. item_at = binary_search(list_of_numbers, search_number)
  41. # Display result of search
  42. if list_of_numbers[item_at] == search_number:
  43. # number has been found
  44. print("{} is in the list at posn {}".format(search_number, item_at))
  45. else:
  46. # only closest number found
  47. print("Closest number is {} at posn {}".format(list_of_numbers[item_at], item_at))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement