Find First and Last Position
Return the first and last index of a target in a sorted array.
Pattern fit
This is the cleanest left-boundary and right-boundary binary-search question because the array is already sorted and the target condition is obvious.
Key observation
The left boundary and right boundary are two different predicates and deserve two separate searches.
Target complexity
O(log n) / O(1)
How to break down the solution cleanly
This is the cleanest left-boundary and right-boundary binary-search question because the array is already sorted and the target condition is obvious.
The left boundary and right boundary are two different predicates and deserve two separate searches.
Write the monotonic predicate in plain English first.
Choose a search interval that definitely contains the answer.
Reference implementation
Python# Generic pattern template
# Find first position where check(mid) is true
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
Common pitfalls
Trying to get both answers in one binary search and making logic fragile.
Returning the first found mid as if it were a boundary.
Common follow-ups
Can you express each search as first true?
How would the answer change if the target did not exist?
Continue with related problems
Build repeatable depth inside the Binary Search cluster before moving on.