# 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))