Binary Search as D&C

Binary search is D&C where you only solve one subproblem.

Divide: Compare target with middle element. Conquer: Search in the left or right half (not both). Combine: No combination needed. The answer comes directly from the subproblem.

function binarySearch(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) / 2
    if arr[mid] == target:
        return mid
    else if arr[mid] < target:
        return binarySearch(arr, target, mid + 1, high)
    else:
        return binarySearch(arr, target, low, mid - 1)

Recurrence: $T(n) = T(n/2) + O(1)$ gives $T(n) = O(\log n)$.