Binary Search in Python

Binary Search is a highly efficient algorithm used to find an element in a sorted array. The main idea behind Binary Search is to repeatedly divide the search interval in half and compare the middle element of the interval with the target value. If the target value matches the middle element, the search is successful. If the target value is less than the middle element, the search continues in the lower half of the array; otherwise, it continues in the upper half.

How Binary Search Works

1. Start with the entire array as the search interval.
2. Find the middle element of the array.
3. Compare the middle element with the target value.
4. If the middle element is equal to the target value, return the index of the middle element.
5. If the target value is less than the middle element, narrow the interval to the lower half of the array.
6. If the target value is greater than the middle element, narrow the interval to the upper half of the array.
7. Repeat the process until the interval is empty.

Python Implementation of Binary Search

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2

        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1

        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1

        # x is present at mid
        else:
            return mid

    # x is not present in array
    return -1

# Example usage:
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binary_search(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")
    

Explanation of the Code

• The function binary_search(arr, x) takes a sorted array arr and a target value x as input.
• It initializes the low and high pointers to the start and end of the array, respectively.
• The middle element is calculated using the formula (high + low) // 2.
• If the middle element is equal to the target value x, the function returns the index of the middle element.
• If the middle element is greater than x, the search continues in the lower half; otherwise, it continues in the upper half.
• If the element is not found, the function returns -1.

Complexity Analysis

Binary Search has a time complexity of O(log n) because the search interval is halved with each iteration. This makes it much faster than linear search algorithms for large datasets.

Space complexity is O(1) because it only requires a constant amount of additional space.