Binary Search!

It is an searching algorithm which can be use only on sorted list or array either in ascending order or descending order.

So now let us understand the binary search algorithm with a help of example: Suppose we have to search the 3rd element i.e index 2 from list = [1, 2, 3, 4, 5, 6, 7,8, 9].

Step 1: Find the mid .

Step 2: If list(mid) = 3(element to be search) → Mid is required index

Step 3: If list(mid) >3 , we simply skip the right part of list and search in left part.

Step 4: If list(mid) <3 , we simply skip the left part of list and search in right part.

Step 5: We repeat step 4 and 5 until we get the required index.

Now let us understand this with the help of above figure:

• As the mid is 4, compare 3 with list(mid)…….mid = (0 + 8) / 2.
• 3 < list(mid), so we ignore right part.
• Now the new mid is 2, compare 3 with list(mid)…….mid = (0 + 3) / 2.
• 3 > list(mid), so we ignore left part.
• Now the new mid is 0, compare 3 with list(mid)…….mid = (2 + 3) / 2.
• 3 == list(mid) → so required index is mid.

Code for binary search is given below in Python language:

def bin(lst, search):
    left, right = 0, len(lst) - 1
    while left <= right:
        mid = (right + left) // 2
        if lst[mid] == search:
            print(mid)
            break
        elif lst[mid] > search:
            right = mid - 1
        else:
            left = mid + 1
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
bin(lst, 3)

Recursive approach for binary search is given below:

def bin(lst, search, left, right):
    while(left <= right):
        mid = (left + right + 1) // 2
        if search == lst[mid]:
            return mid
        elif search > lst[mid]:
            left = mid + 1
        else:
            right = mid - 1
        bin(lst, search, left, right)
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(bin(lst, 3, 0, len(lst) - 1))

Note : I am starting the index from 0 so don’t get confused.

Happy Coding!