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

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/find-first-and-last

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

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

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/find-first-and-last

Repovive

Find First and Last - Binary Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Find First and Last

Locate the range of equal elements.

Using lower bound and upper bound together, you can find the first and last occurrence of a value.

Problem: Find the starting and ending position of a target in a sorted array.

Solution:

function searchRange(arr, target):
    first = lowerBound(arr, target)

    if first == arr.length or arr[first] != target:
        return [-1, -1]

    last = upperBound(arr, target) - 1
    return [first, last]

Example: Find range of $5$ in $[1, 3, 5, 5, 5, 7, 9]$ .

Lower bound of $5$ : index $2$ .
Upper bound of $5$ : index $5$ .
Range: $[2, 4]$ .

Time: $O(\log n)$ for two binary searches.