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

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/upper-bound

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

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

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/upper-bound

Repovive

Upper Bound - Binary Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Upper Bound

Find the first element strictly greater than target.

Upper bound finds the first element strictly greater than the target. Combined with lower bound, you can count occurrences.

Example: Upper bound of $5$ in $[1, 3, 5, 5, 7, 9]$ is index $4$ (the $7$ ).

Counting occurrences: The count of $5$ is upperBound(5) - lowerBound(5) = 4 - 2 = 2.

function upperBound(arr, target):
    low = 0
    high = arr.length

    while low < high:
        mid = low + (high - low) / 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid

    return low

The only difference from lower bound: use <= instead of < when comparing.