Binary Search in Python

Sure, here’s an example implementation of binary search in Python:

def binary_search(arr, target):
    """
    Performs binary search on the given sorted array arr for the target element target.
    Returns the index of the target element if found, otherwise returns -1.
    """
    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

Here’s an example usage of the binary_search function:

arr = [1, 3, 5, 7, 9]
target = 5

index = binary_search(arr, target)
if index == -1:
    print("Element not found")
else:
    print(f"Element found at index {index}")

This implementation assumes that the input array is already sorted in ascending order, and returns the index of the target element if found, otherwise returns -1. The algorithm works by repeatedly dividing the search interval in half until the target element is found or the interval is empty.

Recursive Binary Search:

Sure, here’s an example implementation of recursive binary search in Python:

def binary_search(arr, target):
    """
    Performs binary search on the given sorted array arr for the target element target.
    Returns the index of the target element if found, otherwise returns -1.
    """
    return _binary_search(arr, target, 0, len(arr) - 1)

def _binary_search(arr, target, left, right):
    """
    Helper function for binary search. Performs binary search on the given sorted array arr for the target element target,
    restricted to the interval [left, right].
    Returns the index of the target element if found, otherwise returns -1.
    """
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return _binary_search(arr, target, mid + 1, right)
    else:
        return _binary_search(arr, target, left, mid - 1)

Here’s an example usage of the binary_search function:

arr = [1, 3, 5, 7, 9]
target = 5

index = binary_search(arr, target)
if index == -1:
    print("Element not found")
else:
    print(f"Element found at index {index}")

This implementation uses a helper function _binary_search to perform the actual binary search, taking as input the same arguments as the main function binary_search plus the indices left and right that define the interval to search in. The helper function is called recursively, with the interval being split in half at each recursive call, until the target element is found or the interval is empty.

Complexity:

The time complexity of both iterative and recursive binary search algorithms is O(log n), where n is the length of the input array. This is because at each step of the algorithm, the size of the search interval is divided in half. Therefore, the number of steps required to reach the target element is proportional to the logarithm of the size of the input array.

The space complexity of the iterative binary search algorithm is O(1), because it only requires a constant amount of additional space to store the left and right indices and the mid-point of the search interval.

The space complexity of the recursive binary search algorithm is O(log n), because it requires space proportional to the depth of the recursion, which is also proportional to the logarithm of the size of the input array. This is because each recursive call requires additional space on the call stack to store the arguments and local variables of the function call. However, the space used by the call stack is typically negligible compared to the size of the input array, so the space complexity of the recursive binary search algorithm is still considered to be O(log n).

Conclusion:

Binary search is a fundamental algorithm for searching for an element in a sorted array. It works by repeatedly dividing the search interval in half until the target element is found or the interval is empty. Binary search has a time complexity of O(log n) and a space complexity of O(1) for the iterative implementation, and O(log n) for the recursive implementation.

Binary search is a very efficient algorithm for searching for an element in a sorted array, especially for large arrays. However, it requires that the input array is sorted, which may not always be possible or practical. Additionally, if the array is not sorted, a linear search may be faster than sorting the array and then using binary search.

Overall, binary search is an important algorithm to know and is widely used in computer science and programming.