How does the binary search algorithm work?

Binary search works by analyzing a sorted array, repeatedly dividing the search interval in half.

1. Initialization: The left and right boundaries of the search interval are defined (usually the start and end of the array).
2. Comparison: The middle index of the interval is calculated. The value at this index is compared with the target element.
3. Reducing the interval:
   • If the value in the middle matches the target, the element is found.
   • If the value in the middle is greater than the target, the search continues in the left half of the interval. The right boundary is moved to middle-1.
   • If the value in the middle is less than the target, the search continues in the right half of the interval. The left boundary is moved to middle+1.
4. Repeat: Steps 2 and 3 are repeated until the element is found or the search interval becomes empty.

The algorithm's complexity is O(log n), which is significantly more efficient than linear search for large arrays.

Example implementation in Python:

def binary_search(arr, target):
    """
    Implementation of binary search.
    Takes a sorted array and the target value.
    Returns the index of the element or -1 if not found.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Calculate the middle index
        mid_val = arr[mid]      # Get the value at the middle

        if mid_val == target:
            return mid  # Element found
        elif mid_val < target:
            left = mid + 1  # Target is greater, search in the right part
        else: # mid_val > target
            right = mid - 1 # Target is smaller, search in the left part

    return -1 # Element not found