Python Program for Binary Search

We are everyone aware of  Binary Search. Let's practice with different examples. 

Thumb rule of  Binary Search is that the given list is already sorted 

The bisect module provides efficient ways to maintain and manipulate sorted lists.It is particularly useful for tasks that require frequent insertion and searching in sorted lists.

Example 1 : 

import bisect

arr = [ 2, 3, 4, 10, 40 ] # sorted list

bisect.insort(arr,5) # insort functions help in finding insertion points

print(arr)

                   ⇣ Inserted after 4<5<10

output : [2, 3, 4, 5, 10, 40]

Example 2 . Without bisect module.

arr = [ 2, 3, 4, 10, 40 ]

lookup = 12

start = 0

end = len(arr) -1

for i in range(len(arr)):

    mid = (start + end)// 2

    if arr[mid] >= lookup:

        start -= 1

    else:

        end += 1

    if arr[-1] < lookup:

        print(arr.insert(len(arr),lookup))

       

arr.insert(mid,lookup)

print(f"Inserted value {lookup} in the list ",arr)

                                                        ⇣ Inserted after 10< 12 <40                

Output: # Inserted value 12 in the list [2, 3, 4, 10, 12, 40]

Example 3. Now search the item index in the list  

arr = [ 2, 3, 4, 10, 40 ]

lookup = 10

start = 0

end = len(arr) -1

for i in range(len(arr)):

    mid = (start + end)// 2

    if arr[mid] >= lookup:

        start -= 1

    else:

        end += 1

       

print(mid)

OutPut : 3