bobhig

Binary Search

Feb 12th, 2019
170
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # binary search on sorted list
  2. # returns left (or right) position of value
  3.  
  4.  
  5. import random
  6.  
  7. random_items = []
  8.  
  9. def binary_search(sorted_list, value):
  10.     left = 0
  11.     right = len(sorted_list) - 1
  12.     while left <= right:
  13.         mid = int((left + right)/2)
  14.         if sorted_list[mid] > value:
  15.             right = mid - 1
  16.         elif sorted_list[mid] < value:
  17.             left = mid + 1
  18.         else:
  19.             while sorted_list[mid-1] == value: #alter this for right or left
  20.                 mid -= 1
  21.             mid += 1
  22.             return mid
  23.     return False
  24.  
  25. # populate list
  26. for x in range (0, 100):
  27.     random_items.append(random.randint(0, 100))
  28. sorted_items = sorted(random_items)
  29.  
  30. print(sorted_items)
  31. print(binary_search(sorted_items, 10))
RAW Paste Data