Binary Search - Dynamic Implementation

Problem

Find a target element in a sorted array using binary search algorithm.

Solution

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# Example usage
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)
print(f"Target found at index: {result}")  # Output: 3

Time Complexity

• Time: O(log n) - Each iteration reduces search space by half
• Space: O(1) - Only uses constant extra space

Key Points

1. Array must be sorted - Binary search only works on sorted arrays
2. Prevent overflow - Use left + (right - left) / 2 instead of (left + right) / 2
3. Boundary updates - Always update left = mid + 1 or right = mid - 1
4. Termination condition - Loop continues while left <= right

Common Variations

• Find first occurrence of target
• Find last occurrence of target
• Find insertion position
• Search in rotated sorted array