DSA sheet · Binary Search · Lower & upper bound pattern

First & Last Position of an Element

This is the first problem of a new pattern in the sheet: lower bound / upper bound. Plain binary search stops as soon as it finds the target. Here the array can hold the target many times, and we must report the leftmost and the rightmost copy. The teacher shows the one trick that powers this whole pattern: when mid matches, don't stop. Write the index down and keep searching in one direction. Count Occurrences and Floor & Ceiling (the next problems) are built on exactly this trick.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (incl. lower vs upper bound)
• Part A · Finding the FIRST position
• Part B · Finding the LAST position
• Part C · Putting both together (+ the "right = mid" variant)
• Part D · The same answer using lower_bound / upper_bound
• Part E · Revision page

Part 0 · Before starting

Why binary search works here

Binary search needs one thing: after looking at one element, you must be able to say "the answer is definitely not on this side". A sorted array gives us that. If the middle value is smaller than what we want, everything to its left is even smaller, so the whole left half can be thrown away in one go.

Another way to see it: ask a yes/no question about each cell, like "is nums[i] >= 8?". In a sorted array the answers always line up as no no no yes yes yes. They never jump back and forth. Binary search is just a fast way to find where the answers switch.

left, right and mid

• left (also called low) and right (also called high) are two indexes. The part of the array we are still searching is everything from left to right, both included.
• mid is the index in the middle of that part. We look only at nums[mid] and decide which half to keep.
• The teacher stresses this: we never delete anything from the array. "Throwing away half" just means moving left or right past mid, so that half is no longer between the two pointers.

Why mid = left + (right - left) // 2 and not (left + right) // 2?

Both give the same number. The difference is only in Java/C++, where an int has a maximum (about 2.1 × 10⁹). If left and right are both huge, left + right can go past that maximum and wrap into a negative number (this is called overflow). right - left is never bigger than the array, so left + (right - left) // 2 stays safe.

In Python, integers never overflow, so either form works. We still write the safe form, because the teacher wants it as a habit, and you'll need it the day you write the same thing in Java or C++.

Why while left <= right?

The search area is [left … right]. When left == right, there is still one element in it that we haven't checked. Only when left > right (the pointers have crossed) is the area truly empty. Part A shows a real case where stopping one step early gives the wrong answer.

Lower bound vs upper bound (the name of this pattern)

Take a sorted array and a value x.

• Lower bound of x = the first index whose value is >= x. ("The first place where x could sit.")
• Upper bound of x = the first index whose value is > x, strictly bigger. ("The first place just after all the x's.")
• If no such index exists, the bound is n (one past the end).

Here they are drawn for nums = [5, 7, 7, 8, 8, 10] and x = 8:

  index:   0   1   2   3   4   5
  value:   5   7   7  [8   8]  10
                       ^       ^
          lower bound (3)      upper bound (5)
          = first 8            = first value after the 8s
  first position = lower bound      = 3
  last position  = upper bound - 1  = 4

And for a value that is missing, x = 6: both bounds land on the same index (1, the first 7), because there are zero 6's between them.

The teacher doesn't write a function named lower_bound in this video. She writes "find first" and "find last" directly. Part D shows how her two functions are the same thing as the two bounds.

Part A · Finding the FIRST position

LeetCode 34 · Find First and Last Position of Element in Sorted Array

1The question in simple words

You get an array nums sorted in non-decreasing order. That means each value is bigger than or equal to the one before it, so repeats are allowed (5, 7, 7, 8, 8, 10 is fine). You also get a target.

Return two indexes: where the target appears for the first time, and where it appears for the last time. If the target is not in the array at all, return [-1, -1].

• target 6 on the same array → [-1, -1] (6 is not there).
• empty array, any target → [-1, -1].

LeetCode also asks for an O(log n) solution, so a simple left-to-right scan is not what they want. This part solves only the first half of the answer: the first index.

2What the constraints tell us

• 0 <= nums.length <= 10⁵ → the array can be empty. Our code must return [-1, -1] without crashing. (It does: right starts at −1, so the loop never runs.)
• Values and target are between −10⁹ and 10⁹: very big, and can be negative. The teacher reads this as a warning to compute mid in the overflow-safe way.
• The array is sorted → this is the signal for binary search.

3Intuition: how to think about it

Normal binary search would find an 8 and stop. But it might land on the second 8, not the first.

Picture it like this: every time you land on an 8, you write its index on a sticky note (a variable ans), and then keep searching to the left, because if there is an earlier 8, it can only be on the left side (the array is sorted). If you find another 8 further left, you overwrite the note. When the search area runs out, the note holds the leftmost 8.

Saving the index first is what makes it safe to keep moving: even if the left side has no more 8's, we haven't lost the one we found.

4Building the conditions from examples

The teacher builds the code one case at a time while walking through nums = [5, 7, 7, 8, 8, 10], target 8. Let's do the same.

Start: left = 0, right = 5 → mid = 2

Case 1: nums[mid] < target → go right, left = mid + 1

nums[2] = 7 and we want 8. Since the array is sorted, every 8 must be to the right of this 7. The whole left half (5, 7, 7) is useless, and so is mid itself, because 7 is not 8. So we jump left past mid: left = mid + 1 = 3.

Case 2: nums[mid] == target → save it, then keep going LEFT

New mid = 3 + (5 − 3) // 2 = 4. nums[4] = 8, a match! But is it the first 8? We can't tell yet. There may be another 8 on its left (and in fact there is, at index 3).

• This 8 might be the answer (if there are no more 8's on the left). So save it: ans = mid.
• An earlier 8 can only be on the left, so search the left side: right = mid - 1.

Why the loop must be while left <= right (her long explanation)

Now left = 3 and right = 3. Both pointers are on the same cell. Should we stop?

The teacher says no, check that last cell too. Her reasoning: we haven't looked at this cell yet. It might be another 8 (then the answer improves), or it might be something else (she imagines it being a 6). We can only know which by checking it. If we skip it, we can't tell whether the saved answer is really the first.

In our example it really matters. mid = 3, nums[3] = 8 → ans = 3, right = 2. Now left (3) > right (2): the pointers have crossed, every cell has been considered, and we stop with ans = 3 ✓.

Case 3: nums[mid] > target → go left, right = mid - 1

At first the teacher had only the two cases above, and then she noticed a hole with a new example: nums = [1, 2, 3, 4, 4, 5], target 1.

mid lands on 3, which is bigger than 1. Our code had no rule for this. Since the array is sorted, the 1 must be on the left. And mid itself is not 1, so there's no point keeping it: right = mid - 1. Now we search only [1, 2].

Starting value of ans

We start with ans = -1. If we never land on the target, it's never overwritten, and −1 is exactly what the question wants for "not found".

5Approach steps

1. Set left = 0, right = len(nums) - 1, ans = -1.
2. While left <= right: compute mid = left + (right - left) // 2.
3. If nums[mid] == target: save ans = mid, then search left: right = mid - 1.
4. Else if nums[mid] < target: the target is on the right: left = mid + 1.
5. Else (nums[mid] > target): the target is on the left: right = mid - 1.
6. When the pointers cross, return ans.

6Code (Python)

def find_first(nums, target):
    left, right = 0, len(nums) - 1
    ans = -1                                  # -1 means "not found yet"
    while left <= right:
        mid = left + (right - left) // 2      # overflow-safe habit
        if nums[mid] == target:
            ans = mid                         # might be the first one: save it
            right = mid - 1                   # but look for an earlier one on the LEFT
        elif nums[mid] < target:
            left = mid + 1                    # target is on the right
        else:
            right = mid - 1                   # target is on the left
    return ans

7Code line by line

8Dry run (hand table)

nums = [5, 7, 7, 8, 8, 10], target = 8.

Her second example, [1, 2, 3, 4, 4, 5], target 1: mid=2 (3 > 1) → right=1; mid=0 (1 = 1) → ans=0, right=−1; crossed → 0 ✓.

9Complexity & remember

• Time O(log n): each step halves the search area. For n = 10⁵, that's about 17 steps.
• Space O(1): only a few variables.

Part B · Finding the LAST position

1The question

Same array, same target. Now find the index of the last copy of the target (4 for target 8 in [5, 7, 7, 8, 8, 10]), or −1.

2Constraints

Same as Part A: possibly empty, big values, sorted.

3Intuition: what changes

The teacher asks: "can the same code give us the last position?" Go back to step 2 of the dry run, where mid = 4 landed on an 8. For the first position we went left. But if we want the last position, a later 8 could only be on the right. So we still save the index, but we move the other way.

That's why one function can't do both jobs: at a match it must choose a direction. So we write a second function with one line changed.

4The conditions

The same reasoning about <= applies: the last unchecked cell might be one more 8 further right, so check it.

5Approach steps

1. Same setup: left = 0, right = n - 1, ans = -1.
2. On a match: save ans = mid, then search right: left = mid + 1.
3. Too small → left = mid + 1. Too big → right = mid - 1.
4. Return ans.

6Code (Python)

def find_last(nums, target):
    left, right = 0, len(nums) - 1
    ans = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            ans = mid                         # might be the last one: save it
            left = mid + 1                    # ONLY CHANGE: look for a later one on the RIGHT
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans

7Code line by line

8Dry run (hand table)

nums = [5, 7, 7, 8, 8, 10], target = 8.

Her second example [1, 2, 3, 4, 4, 5], target 1: mid=2 (3 > 1) → right=1; mid=0 (match) → ans=0, left=1; mid=1 (2 > 1) → right=0; crossed → 0. First = last = 0, because 1 appears once.

9Complexity & remember

O(log n) time, O(1) space, same as Part A.

Part C · Putting both together

1The question

Return [first, last], which is the full LeetCode answer.

2Constraints

An empty array must give [-1, -1], and both helpers already do that.

3Intuition

The teacher's final code has two helper functions (find first, find last). The main function calls both, stores the results in first and last, and returns them as a pair. If the target is missing, both helpers return −1 on their own, so we get [-1, -1] with no extra check.

4Building it: walk a "not found" case

target 6 in [5, 7, 7, 8, 8, 10], inside find_first:

Notice where left ended: index 1, the first value ≥ 6. That's the lower bound of 6 from Part 0. Binary search always leaves left at the switch point.

5Approach steps

1. first = find_first(nums, target)
2. last = find_last(nums, target)
3. Return [first, last].

6Code (Python)

class Solution:
    def searchRange(self, nums, target):
        first = self.findFirst(nums, target)
        last = self.findLast(nums, target)
        return [first, last]

    def findFirst(self, nums, target):
        left, right = 0, len(nums) - 1
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                ans = mid
                right = mid - 1          # go left for an earlier copy
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return ans

    def findLast(self, nums, target):
        left, right = 0, len(nums) - 1
        ans = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                ans = mid
                left = mid + 1           # go right for a later copy
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return ans

The other style she mentions: keep mid inside the range (right = mid)

Instead of saving mid in ans, you can keep it inside the search area by setting right = mid. Then the loop runs while left < right and ends when both pointers meet. At the end, you check whether that one cell is the target.

def find_first_v2(nums, target):
    if not nums:
        return -1
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2          # lower middle
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid                           # mid may be the first copy: keep it
    return left if nums[left] == target else -1

def find_last_v2(nums, target):
    if not nums:
        return -1
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left + 1) // 2      # UPPER middle (see doubt)
        if nums[mid] > target:
            right = mid - 1
        else:
            left = mid                            # mid may be the last copy: keep it
    return left if nums[left] == target else -1

7Code line by line (main function)

8Dry run of the whole thing

1. searchRange([5,7,7,8,8,10], 8) → findFirst gives 3 (Part A table) → findLast gives 4 (Part B table) → [3, 4].
2. searchRange([5,7,7,8,8,10], 6) → both helpers never match → [-1, -1].
3. searchRange([], 0) → right = −1, both loops skip → [-1, -1].
4. searchRange([1], 1) → mid=0 matches in both → [0, 0].

9Complexity & remember

• Time: log n for the first search + log n for the second = 2 log n. Constants are dropped, so it's O(log n). The teacher points out this is still logarithmic, much faster than a linear scan.
• Space O(1).

Part D · The same answer using lower_bound / upper_bound

Not shown in the video. This is added to connect her code to the pattern's name.

1The idea

From Part 0: first position = lower bound (first index with value ≥ target), and last position = upper bound − 1 (one before the first index with value > target). Each bound is one binary search that never needs an "equal" case.

2Code (Python)

def lower_bound(nums, x):          # first index with nums[i] >= x  (n if none)
    left, right = 0, len(nums) - 1
    ans = len(nums)
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= x:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

def upper_bound(nums, x):          # first index with nums[i] > x   (n if none)
    left, right = 0, len(nums) - 1
    ans = len(nums)
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] > x:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

def search_range(nums, target):
    lb = lower_bound(nums, target)
    if lb == len(nums) or nums[lb] != target:
        return [-1, -1]                       # target is missing
    return [lb, upper_bound(nums, target) - 1]

The only difference between the two bounds is >= vs >. Python's built-in bisect.bisect_left(nums, x) is the lower bound and bisect.bisect_right(nums, x) is the upper bound, which is handy for checking your answer. But in an interview, write the loop yourself.

3Complexity

Still two binary searches: O(log n) time, O(1) space.

Part E · Revision page

s = Solution()
print(s.searchRange([5, 7, 7, 8, 8, 10], 8))   # [3, 4]
print(s.searchRange([5, 7, 7, 8, 8, 10], 6))   # [-1, -1]
print(s.searchRange([], 0))                    # [-1, -1]
print(s.searchRange([1, 2, 3, 4, 4, 5], 1))    # [0, 0]
print(s.searchRange([2, 2, 2, 2], 2))          # [0, 3]

Based on this video: Find First and Last Position of Element in Sorted Array