Advertisement
timber101

birarySearchAndMore

Dec 28th, 2020
1,036
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #  binary search
  2. #  needs a sorted list
  3.  
  4. sorted_list = [1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
  5. #[1,2,4,5,8]
  6. def binary_search(asorted_list, avalue):
  7.     left = 0                    # left to 0
  8.     right =len(asorted_list)-1  # right to highest index in list
  9.     while left <= right:        # loop that ends when left > right
  10.         mid = int((left + right)/2) # mid to int between left and right
  11.         #print(left, right, mid)
  12.         if asorted_list[mid] > avalue:
  13.             right = mid - 1       # if sorted_list[mid] > value  set right to mid - 1
  14.             rightdist=round(abs(asorted_list[right]-avalue),3) # nummerical distance from mid
  15.             #print(left, right, mid)
  16.         elif asorted_list[mid] < avalue:
  17.             left = mid + 1
  18.             leftdist=round(abs(asorted_list[left]-avalue),3) # nummerical distance from mid
  19.             #print(left, right, mid)
  20.         else:
  21.             countmid = (asorted_list.count(asorted_list[mid]))  # count number of items
  22.             firstmid =(asorted_list.index(asorted_list[mid]))   # index of the first item
  23.             lastmid = firstmid + countmid -1                    # index of the last item
  24.            
  25.             return (f"{avalue} was found at position {mid}, {avalue} appears {countmid} times, first occurence postn {firstmid}, last occurence postn {lastmid}  ")
  26.             # location of a found item
  27.            
  28.     if leftdist > rightdist:
  29.         nearno = asorted_list[right]
  30.         pos = right
  31.     else:
  32.         nearno = asorted_list[left]
  33.         pos = left
  34.     return (f"The search for {avalue} was not found, nearest number is {nearno} at position {pos}")
  35.    
  36.    
  37. print(binary_search(sorted_list,4.5))
Advertisement
RAW Paste Data Copied
Advertisement