Advertisement
Antypas

Binary search ordered list multiple identical values

Apr 18th, 2020
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.28 KB | None | 0 0
  1. #Binary search of ordered lists with multiple identical values
  2.  
  3. sorted_list=[1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
  4. print( "Length of sorted list is " ,len(sorted_list))
  5. print("Sorted List: ", sorted_list)
  6.  
  7. def binary_search(sorted_list, value):
  8.     left = 0
  9.     right = len(sorted_list) - 1
  10.     while left <= right:
  11.         mid = int((left + right)/2)  # mid = (left+right)//2
  12.         if sorted_list[mid] > value:
  13.             right = mid - 1
  14.         elif sorted_list[mid] < value:
  15.             left = mid + 1
  16.         elif sorted_list[mid] == value:
  17.             leftmid = mid
  18.             while sorted_list[leftmid-1] == value:
  19.                 leftmid = leftmid-1
  20.             rightmid = mid        
  21.             while sorted_list[rightmid+1] == value:
  22.                 rightmid = rightmid+1
  23.             return leftmid , rightmid
  24.     return False
  25.  
  26. value = 4  #can change the search value here
  27. temp =  binary_search(sorted_list, value )
  28. if temp != False:
  29.     print("Value > ", value)
  30.     print("left index is " + str(temp[0]))
  31.     print("right index is " + str(temp[1]))
  32. else:
  33.     print("Value > ", value)
  34.     print(temp)
  35.  
  36. '''
  37. Sample output:
  38. Length of sorted list is  13
  39. Sorted List:  [1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
  40. Value >  4
  41. left index is 3
  42. right index is 7
  43. '''
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement