Binary Search | Algorithm

Binary Search is one of the most popular searching algorithms. We use this to search specific elements on a sorted list. It doesn’t matter it’s ascending or descending. A binary search is not applicable on an unsorted list. It’s a fast and widely used algorithm.

In real life, you might already use this algorithm without knowing. By the way, let’s see a visual of how binary search work.

Steps for this algorithm are simple:

• Find the mid point.
• If mid is equal to the search value, then stop.
• If search vaue is greater than the mid, then search on the right.
• If search value is less than the mid, the search on the left.
• Repeat

Let’s see how can we implement this algorithm using Python.

def bin_search(lst, value):
    
    begin = 0
    end = len(lst) - 1
    index = None
    
    while begin <= end:
        mid = (begin + end) // 2
        
        if value == lst[mid]:
            index = mid
            break
        elif value > lst[mid]:
            begin = mid + 1
        elif value < lst[mid]:
            end = mid - 1
            
    return index
    
arr = [1, 3, 5, 7, 10, 12]
res = bin_search(arr, 3)
print(res) # Result = 1

Binary search is much faster than linear search. The time complexity of this algorithm is O(log n).

Tags: Binary SearchSearch Algorithm