#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/binary-search-as-d-c

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/divide-and-conquer/binary-search-as-d-c

Repovive

Binary Search as D&C - Divide and Conquer | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Binary Search as D&C

D&C with only one subproblem.

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)$ .