How does the binary search algorithm work?

The binary search algorithm is an efficient method for finding the position of a target element in a sorted array (or list).

Working principle:

1. Start of search: Define the search interval boundaries - the beginning (left) and end (right) of the array.
2. Calculate the middle: At each iteration, determine the middle index (middle) of the current interval: middle = (left + right) / 2.
3. Comparison: Compare the target element with the element at index middle.
   • If the target element equals the element at index middle, the search is complete, and the element is found.
   • If the target element is less than the element at index middle, narrow the search to the left half of the interval: right = middle - 1.
   • If the target element is greater than the element at index middle, narrow the search to the right half of the interval: left = middle + 1.
4. Repeat: Steps 2 and 3 are repeated until the target element is found or the search interval becomes empty (left > right).
5. Result: If the element is found, its index is returned. If not, an indicator of absence (e.g., -1) is returned.

Advantages:

• High speed (logarithmic complexity O(log n)), especially for large data sets.

Disadvantages:

• Requires pre-sorting of the array.
• Only applicable to collections with random access by index.

Example implementation in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1 # Initialize search boundaries
    while left <= right: # Continue while the search interval is not empty
        mid = (left + right) // 2 # Calculate the middle index
        if arr[mid] == target:
            return mid # Element found, return index
        elif arr[mid] < target:
            left = mid + 1 # Target in the right half
        else:
            right = mid - 1 # Target in the left half
    return -1 # Element not found