Understanding the Binary Search Algorithm: A Step-by-Step Guide with Python Example

Binary search is an efficient algorithm for finding a specific value in a sorted list or array. In this blog, we’ll take a closer look at how the binary search algorithm works and how you can implement it in your own code.

How Binary Search Works

Binary search works by repeatedly dividing the search range in half until the value is found or the range is empty. Here’s how the binary search algorithm works, step by step:
1. Initialize: Start by initializing two variables, low and high, to represent the range of possible values. Set low to the first index of the list and high to the last index of the list.
2. Check if the range is valid: Check if low is less than or equal to high. If it is not, then the value is not in the list and the algorithm terminates.
3. Calculate the middle index: Calculate the middle index of the current range by adding low and high and dividing by 2.
4. Check the middle element: Check if the element at the middle index is equal to, less than, or greater than the value you are searching for.
5. Update the range: If the middle element is equal to the value, then you have found the value and the algorithm terminates. If the middle element is less than the value, then update low to be one more than the middle index. If the middle element is greater than the value, then update high to be one less than the middle index.
6. Repeat: Repeat steps 2-5 until either the value is found or low becomes greater than high.

Implementing Binary Search in Python
Here’s an example of how you can implement binary search in Python:

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

print(binary_search([10, 20, 30, 40, 50], 30))

This function takes a sorted list and a value as arguments and returns the index of the value in the list using binary search. If the value is not found in the list, it returns -1.

In conclusion, Binary search is a powerful algorithm that can be used to quickly find values in sorted lists or arrays. By understanding how it works and how to implement it in your own code, you can make your programs more efficient and effective.
I hope this blog has helped you understand binary search better! If you have any questions or comments, feel free to leave them below.