Binary Search

Binary search is a more efficient searching algorithm suitable for sorted lists. It repeatedly divides the search interval in half until the target value is found.

Steps:

1. Start with the entire sorted list.
2. Compute the middle element of the list.
3. If the middle element is equal to the target value, return its index.
4. If the middle element is less than the target value, search in the right half of the list.
5. If the middle element is greater than the target value, search in the left half of the list.
6. Repeat steps 2-5 until the target value is found or the search interval is empty.

 

def binary_search(arr, target, low, high):
    """
    Perform binary search recursively to find the target value in the given sorted list.

    Parameters:
        arr (list): The sorted list to be searched.
        target: The value to be searched for.
        low (int): The lower index of the search interval.
        high (int): The upper index of the search interval.

    Returns:
        int: The index of the target value if found, otherwise -1.
    """
    if low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search(arr, target, mid + 1, high)
        else:
            return binary_search(arr, target, low, mid - 1)
    else:
        return -1

# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(sorted(arr), target, 0, len(arr) - 1)
if result != -1:
    print(f"Binary Search: Element found at index {result}")
else:
    print("Binary Search: Element not found")