Binary Search is one of the most popular searching algorithms. We use this to search specific elements on a sorted list. 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.
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).