Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #Binary search of ordered lists with possibly multiple
- #identical values, return the index of the closest value,
- #when the actual value is not found
- from random import randint
- #quick way to create an ordered list of numbers.
- #(notice largest possible number is 99)
- #sorted_list = [i + randint(0,9) for i in range(0,100,10)]
- sorted_list=[1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
- #sorted_list = [2]
- #sorted_list = [1,2,3,5,6,7]
- print( "Length of sorted list is " ,len(sorted_list))
- print("Sorted List: ", sorted_list)
- def binary_search(sorted_list, value):
- left = 0
- right = len(sorted_list) - 1
- while left <= right:
- mid = int((left + right)/2) # mid = (left+right)//2
- if sorted_list[mid] > value:
- right = mid - 1
- if value > sorted_list[right]:
- return right, right+1
- elif sorted_list[mid] < value:
- left = mid + 1
- if value < sorted_list[left]:
- return left-1, left
- elif sorted_list[mid] == value:
- leftmid = mid
- while sorted_list[leftmid-1] == value:
- leftmid = leftmid-1
- rightmid = mid
- while sorted_list[rightmid+1] == value:
- rightmid = rightmid+1
- return leftmid , rightmid
- return False
- value = 4.3
- temp = binary_search(sorted_list, value )
- if temp != False:
- print("Value > ", value)
- print("left index is " + str(temp[0]))
- print("right index is " + str(temp[1]))
- else:
- print("Value > ", value)
- print(temp)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement