LeetCode 34 · Binary search

Find First and Last Position of Element in Sorted Array, explained with a picture

All copies of one book on a sorted shelf.

Binary search
▶ Watch it step by step

The problem

In a sorted list, find the first and last position of a target value, or [−1, −1].

Input:  [5, 7, 7, 8, 8, 8, 8, 10, 12], target = 8
Output: [3, 6]

Picture it

Picture a library shelf with several copies of the same book in a row. Run binary search twice: once leaning left to find the first copy, once leaning right to find the last copy.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Two binary searches (lower bound and upper bound). O(log n).

Python solution

def search_range(a, t):
    def bound(first):
        lo, hi, ans = 0, len(a) - 1, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if a[mid] == t:
                ans = mid
                if first: hi = mid - 1   # keep looking left
                else: lo = mid + 1       # keep looking right
            elif a[mid] < t:
                lo = mid + 1
            else:
                hi = mid - 1
        return ans
    return [bound(True), bound(False)]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.