Python – Binary Search Algorithm

Python – Binary Search Algorithm

Binary Search is an efficient searching algorithm used to find a specific element in a sorted collection. It works by repeatedly dividing the search range in half, eliminating half of the remaining elements at each step.

Binary Search is much faster than Linear Search for large datasets, but it requires the collection to be sorted. It is a divide-and-conquer algorithm that reduces the search space by half in each iteration.

Algorithm Steps

The steps of the Binary Search algorithm are as follows:

1. Start with the entire sorted collection as the search range.
2. Calculate the middle index of the current search range.
3. If the middle element is the target, return its index.
4. If the target is less than the middle element, repeat the search on the left half of the current range.
5. If the target is greater than the middle element, repeat the search on the right half of the current range.
6. Repeat steps 2-5 until the target is found or the search range becomes empty.
7. If the search range becomes empty, the target is not in the collection.

Python Program for Binary Search

In this Python program, we define a function binary_search that takes a sorted list arr and a target value target. It returns the index of the target value in the list or -1 if the value is not found.

Python Program

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_value = arr[mid]

        if mid_value == target:
            return mid
        elif mid_value < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

if __name__ == "__main__":
    sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
    target_value = 7
    result = binary_search(sorted_list, target_value)
    print(f"Index of target {target_value} in the array is: {result}")

Output

Index of target 7 in the array is: 3

Use Cases for Binary Search

Binary Search is suitable for scenarios where:

• The collection is sorted.
• Efficiency is crucial, especially for large datasets.
• There’s a need to quickly determine if an element is present in the collection.
• Searching for elements in arrays, lists, or other sorted structures.

Summary

Binary Search is a powerful algorithm for efficiently finding elements in a sorted collection. In this tutorial, we have learnt the steps for Binary Search, defined a Python function that implements the Binary Search algorithm, and seen its usage.