Binary Search Algorithm

Binary Search is an efficient algorithm for finding an element in a sorted array by repeatedly dividing the search interval in half.

How Binary Search Works

• Start with initial low and high pointers marking the array segment.
• Find the middle element and compare it with the target.
• If match found, return the index.
• If not, either search the left half if the target is smaller or the right half if greater.
• Repeat the process until the target is found or the segment size reduces to zero.

Iterative Implementation 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 Example
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print("Element not found")

Recursive Implementation in Python

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid+1, right)
    else:
        return binary_search_recursive(arr, target, left, mid-1)

# Usage Example
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print("Element not found")

Time Complexity

• Best case: O(1) when the target is at the middle.
• Worst & average case: O(log n) due to halving the search space.

Applications

• Used in searching large sorted datasets efficiently.
• Basis for many advanced algorithms and data structures (like binary search trees).
• Effective in real-time systems and databases.