27. Binary Search: Requirement and Implementation (O(log N))

Binary Search is vastly superior to Linear Search, but it has one strict requirement: the data must be sorted.

Concept

Binary Search eliminates half of the remaining search space at every step. It works by checking the middle element of the current range.

1. Compare the target value with the middle element.
2. If they match, return the middle index.
3. If the target is smaller, repeat the process on the left half.
4. If the target is larger, repeat the process on the right half.

Implementation (Iterative)

python def binary_search(arr, target): low = 0 high = len(arr) - 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1  # Search right half
    else:
        high = mid - 1 # Search left half
return -1

Efficiency: O(log N)