Explain the working principle of the binary search algorithm and when it is used.

The binary search algorithm works on a sorted array or list. The idea is to repeatedly divide the search area in half and compare the target element with the middle element. If the target is less than the middle, the search continues in the left half; if greater, in the right half. This process repeats until the element is found or the search area becomes empty.

Binary search is used when you need to quickly find an element in a sorted data structure. Its complexity is O(log n), which is much more efficient than linear search for large arrays.

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
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Usage
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7))  # Outputs 3