LeetCode 34 Find First and Last Position of Element - Example and Complexity Analysis

Trace nums = [1, 2, 2, 2, 3] with target = 2.

Find leftmost: left = 0, right = 4. mid = 2. nums[2] = 2 == target. Record first = 2. Search left: right = 1.

left = 0, right = 1. mid = 0. nums[0] = 1 < target. Search right: left = 1.

left = 1, right = 1. mid = 1. nums[1] = 2 == target. Record first = 1. Search left: right = 0.

left = 1 > right = 0. Done. Leftmost = 1.

Find rightmost: Similar process, but when finding target, search right. Rightmost = 3.

Return [1, 3].

Two binary searches, each $O(\log n)$. Total: $O(\log n)$ time, $O(1)$ space.