Understanding Binary Search and its implementation in Python

[vickttor]

When we need to search for a specific item in a large list of items, we usually start at the beginning of the list and check each item until we find the desired one. This approach is called linear search, but it can become very time-consuming for larger lists.

An alternative approach is binary search. It is a very efficient algorithm that works on sorted lists. Binary search is also known as logarithmic search as it reduces the search space by half after each iteration.

How Binary Search works

The idea behind binary search is straightforward. Given a sorted list of items, we first take the middle element of the list. If the middle element is the desired element, we return its index. If the desired element is less than the middle element, we search the left half of the list. If it is greater than the middle element, we search the right half of the list. We keep repeating this process until we find the desired element or the list is empty.

Here is an example of binary search on a sorted list of integers:

def binary_search(arr, target):
  low, high = 0, len(arr) - 1
  while low <= high:
    mid = (low + high) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
        
  return -1

The binary_search function takes two arguments: the sorted list and the target element we want to find. The function first sets the low and high indices to the beginning and end of the list, respectively. We keep dividing the search range by two until we find the target element.

Big O Notation and Binary Search

Big O notation is a way of measuring the efficiency of an algorithm in terms of the size of its input. In other words, Big O notation tells us how much time an algorithm takes to execute as the size of the input grows.

For binary search, the worst-case scenario is when the target element is not present in the list. In this case, the search will continue until the list is empty. The number of steps required to perform a binary search on a list of n elements can be expressed as O(log n).

This means that as the size of the list grows, the time taken to perform a binary search increases logarithmically. In comparison, a linear search would take O(n) time, which is much slower than O(log n) for large values of n.

In conclusion, binary search is a very efficient algorithm for searching sorted lists, and it has a time complexity of O(log n) in the worst case. By using binary search, we can save a significant amount of time when searching through large lists of data.