Advertisement
Antypas

Binary search ordered identical closest

Apr 19th, 2020
314
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.56 KB | None | 0 0
  1. #Binary search of ordered lists with possibly multiple
  2. #identical values, return the index of the closest value,
  3. #when the actual value is not found
  4.  
  5. from random import randint
  6. #quick way to create an ordered list of numbers.
  7. #(notice largest possible number is 99)
  8. #sorted_list = [i + randint(0,9) for i in range(0,100,10)]
  9. sorted_list=[1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
  10. #sorted_list = [2]
  11. #sorted_list = [1,2,3,5,6,7]
  12. print( "Length of sorted list is " ,len(sorted_list))
  13. print("Sorted List: ", sorted_list)
  14.  
  15. def binary_search(sorted_list, value):
  16.     left = 0
  17.     right = len(sorted_list) - 1
  18.     while left <= right:
  19.         mid = int((left + right)/2)  # mid = (left+right)//2
  20.         if sorted_list[mid] > value:
  21.             right = mid - 1
  22.             if value > sorted_list[right]:
  23.                 return right, right+1
  24.         elif sorted_list[mid] < value:
  25.             left = mid + 1
  26.             if value < sorted_list[left]:
  27.                 return left-1, left
  28.         elif sorted_list[mid] == value:
  29.             leftmid = mid
  30.             while sorted_list[leftmid-1] == value:
  31.                 leftmid = leftmid-1
  32.             rightmid = mid        
  33.             while sorted_list[rightmid+1] == value:
  34.                 rightmid = rightmid+1
  35.             return leftmid , rightmid
  36.     return False
  37.  
  38. value = 4.3
  39. temp =  binary_search(sorted_list, value )
  40. if temp != False:
  41.     print("Value > ", value)
  42.     print("left index is " + str(temp[0]))
  43.     print("right index is " + str(temp[1]))
  44. else:
  45.     print("Value > ", value)
  46.     print(temp)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement