Can you explain the principle of the binary search algorithm and how it finds the desired value in a sorted array?

The binary search algorithm works only with a sorted array and allows you to quickly find the desired value by halving the search area at each step.

Working principle:

1. The middle element of the array is determined.
2. If the middle element is equal to the desired value — the search is complete.
3. If the desired value is less than the middle, the search continues in the left half of the array.
4. If greater — in the right half.
5. The process repeats recursively or iteratively until the element is found or the search area becomes empty.

Example in Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # index of the found element
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # element not found

# Usage example
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 5))  # Output: 2