Explain the working principle of binary search algorithm and its main characteristics.

Binary search is an algorithm for finding an element in a sorted array or list.

How it works:

• First, the middle element of the array is selected.
• If the sought element equals the middle, the search ends successfully.
• If the sought element is less than the middle, the search continues in the left (smaller) half of the array.
• If it is greater, in the right (larger) half.
• The process repeats recursively or iteratively until the element is found or the subarray for searching is exhausted.

Main characteristics:

• Requires the array to be sorted.
• Time complexity — O(log n), which is significantly faster than linear search.
• Effective for large data volumes.

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  # element not found

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