Coding interview problems › Binary Search

🔍 Binary Search Medium

Find First and Last Position of an Element

Find the first and last position of a target in a sorted array with two binary searches, lower and upper bound, in O(log n). Tested Python and a live visual.

Also searched as: first and last occurrence of an element in a sorted array · lower bound and upper bound · count occurrences in sorted array

🔍

Try it live Free

Binary Search

Run the search on a sorted array and watch how changing a single comparison decides which side the range collapses towards; that is the whole difference between the first-occurrence and last-occurrence searches.

Open the playground →

The problem

Given a sorted list of integers that may contain duplicates and a target, return [first, last]: the index of its first and last occurrence. If the target does not appear, return [-1, -1]. The solution must run in O(log n).

Inputnums = [2, 4, 4, 4, 9], target = 4
Output[1, 3]
Inputnums = [2, 4, 4, 4, 9], target = 5
Output[-1, -1]

The key insight

Run binary search twice, each time looking for a boundary rather than any match. The first occurrence is the first index with value at least the target. The last occurrence is one less than the first index with value greater than the target. The same helper handles both with one changed comparison.

Brute force first: Finding any match with binary search and then walking left and right is O(n) in the worst case, for example when every element equals the target.

Step-by-step approach

  1. Write a helper first_at_least(x) that returns the first index whose value is at least x, using a half-open [lo, hi) binary search.
  2. Let left = first_at_least(target).
  3. If left is out of range or nums[left] != target, the target is absent: return [-1, -1].
  4. Let right = first_at_least(target + 1) - 1; for integers this is the last index holding the target.
  5. Return [left, right].

Python solution

PYTHON 3tested
def search_range(nums, target):
    def first_at_least(x):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    left = first_at_least(target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = first_at_least(target + 1) - 1   # last index still == target
    return [left, right]

Complexity

TimeO(log n)
SpaceO(1)

Two binary searches of O(log n) each is still O(log n). Neither search depends on how many copies of the target there are.

Common mistakes

Frequently asked questions

What is the time and space complexity?

Two binary searches give O(log n) time and O(1) extra space, even when the target fills the whole array.

How do I count how many times the target appears?

Once you have the range, the count is right - left + 1, or 0 when the target is absent. That is O(log n), much faster than counting with a loop.

Can I use bisect for this?

Yes: bisect_left(nums, target) gives the first index and bisect_right(nums, target) - 1 gives the last. Interviewers usually want to see you write the boundary search yourself.

Why not use the classic lo <= hi binary search?

You can, by recording a match and continuing left (or right) instead of returning. The half-open boundary version avoids that extra bookkeeping and is easier to get right.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.