Find First and Last Position of Element in Sorted Array | Leetcode 34 | Optimal Binary Search

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Here’s the [Problem Link] to begin with.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Brute Force Solution (Linear Scan)

Intuition & Approach

Walk through every element:

1. As soon as you encounter target for the first time, store the index as first.
2. Keep updating last while subsequent occurrences appear.
3. After the loop ends, return [first, last] (both stay -1 if the loop never hits target).

Code Implementation

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        first = -1   # left-most index of target
        last = -1    # right-most index of target

        # Scan the whole array
        for i in range(len(nums)):
            if nums[i] == target:
                # record the first time we see the target
                if first == -1:
                    first = i
                # always update last until the loop ends
                last = i

        return [first, last]

Code Explanation

• The loop visits each element exactly once.
• Conditional checks update first only once and last for every hit, so when the loop finishes last really is the right-most match.

Dry Run (nums = [2,2,3,3,3,4], target = 3)

Returns [2, 4].

Time & Space Complexity

• Time: O(n) – each element inspected once.
• Space: O(1) – only two indices stored.

Conclusion

Works fine on small arrays; however, scanning every element is unnecessary when binary search can pinpoint the boundaries in O(log n).

Optimal Solution (Two Binary Searches)

Intuition & Approach

Exploit the array’s sorted order with two tailored binary searches:

1. Left boundary search – find the first index where nums[index] == target.
2. Right boundary search – find the last index where nums[index] == target.

Both searches differ only in the direction they continue after a match:

• When you hit target,
  • Left search keeps moving left (high = mid - 1) to see if an earlier match exists.
  • Right search keeps moving right (low = mid + 1) to see if a later match exists.

Code Implementation

class Solution:
    # ---------- helper to find left-most occurrence ----------
    def binarySearchLeft(self, nums, target):
        n          = len(nums)
        low, high  = 0, n - 1
        index      = -1              # default: not found

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                index = mid          # potential left boundary
                high  = mid - 1      # continue searching left
            elif nums[mid] > target:
                high  = mid - 1      # target is in the left half
            else:                    # nums[mid] < target
                low   = mid + 1      # target is in the right half
        return index

    # ---------- helper to find right-most occurrence ----------
    def binarySearchRight(self, nums, target):
        n          = len(nums)
        low, high  = 0, n - 1
        index      = -1              # default: not found

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                index = mid          # potential right boundary
                low   = mid + 1      # continue searching right
            elif nums[mid] > target:
                high  = mid - 1
            else:                    # nums[mid] < target
                low   = mid + 1
        return index

    # ---------- main driver ----------
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ext_left = self.binarySearchLeft(nums, target)
        # if the target never appears, no need for the second search
        if ext_left == -1:
            return [-1, -1]

        ext_right = self.binarySearchRight(nums, target)
        return [ext_left, ext_right]

Code Explanation

• binarySearchLeft stores any match in index but keeps shrinking the window to the left to ensure it finds the earliest one.
• binarySearchRight mirrors the logic, moving the window to the right after a match.
• If the first search returns -1, the target doesn’t exist, so you can skip the second search.

Dry Run (nums = [5,7,7,8,8,10], target = 8)

• Left search
  • mid = 2 → 7 < 8 → move right
  • mid = 4 → 8 found → store 4, search left → high = 3
  • mid = 3 → 8 found → store 3, search left → high = 2 → stop → left = 3
• Right search
  • mid = 2 → 7 < 8 → move right
  • mid = 4 → 8 found → store 4, search right → low = 5
  • mid = 5 → 10 > 8 → move left → high = 4 → stop → right = 4
• Return [3, 4].

Time & Space Complexity

• Time: O(log n) + O(log n) ≈ O(log n) – two binary searches.
• Space: O(1) – constant extra storage.

Conclusion

Using two directional binary searches gives the exact first and last indices in logarithmic time and constant space, making it the standard interview-grade solution for this problem.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.