Fast and Efficient Search Method, Binary Search

Binary Search is an efficient search algorithm that halves the search space at every step.

In this lesson, we will explore the concept of the binary search algorithm and how to implement it in Python.

Binary search can be used only on a sorted list.

First, you check the middle value of the list. If this value matches the value you are looking for, the search is complete.

If the value to be searched is smaller, the search continues on the left half of the list. If it is larger, the right half of the list is searched.

This process is repeated, halving the list each time, until the value is found or the list can no longer be halved.

The biggest advantage of binary search is its speed because each step cuts the search space in half.

For instance, with 1000 pieces of data, a linear search starting from the first element and going to the last would require up to 1000 comparisons.

However, a binary search would need at most 10 comparisons to find the value.

Now let's see how we can implement binary search in Python.

The following code illustrates a basic implementation of the binary search algorithm.

Copy
def binary_search(arr, target):
    # Start and end indices of the search range
    left, right = 0, len(arr) - 1 
    
    # Repeat until the search range is narrowed down
    while left <= right:
        # Calculate the middle index
        mid = (left + right) // 2
        # Check the middle value
        mid_value = arr[mid]
        
        # If the middle value matches the target value
        if mid_value == target:
            # Return the index
            return mid
        # If the middle value is less than the target value
        elif mid_value < target:
            # Search the right half
            left = mid + 1
        # If the middle value is greater than the target value
        else:
            # Search the left half
            right = mid - 1
    
    return -1  # Return -1 if the value is not found

# Sorted list
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

# Find 7 using binary search
result = binary_search(numbers, 7)

# Output: 3 (value 7 is at index 3)
print(f"Index of the target value: {result}")

• left and right: Variables that define the search range of the list. Initially, they point to the start (0) and the end (len(arr) - 1) of the list respectively.

• mid: Calculates the middle index of the search range. (left + right) // 2 is the code to find the midpoint.

• mid_value: Refers to the value at the middle index. This value is compared with the target value.

• left = mid + 1: If the target value is greater than the middle value, the search range narrows to the right half.

• right = mid - 1: If the target value is smaller than the middle value, the search range narrows to the left half.

• return -1: If the value is not found, -1 is returned to indicate a failed search.