Find first and last position of element in sorted array

You're halfway through a Google phone screen when the interviewer says, "Given a sorted array, find the starting and ending positions of a target value. Oh, and it needs to run in O(log n)." You know binary search can find an element in O(log n), but finding the boundaries of a range of duplicates? That requires a subtle twist on the classic algorithm. This problem, also known as "Find First and Last Position of Element in Sorted Array" on other platforms, is a favorite at companies like Adobe, Meta, and Google because it reveals whether you truly understand binary search or just memorized the template.

TL;DR

Run two modified binary searches: one that keeps searching left after finding the target (to locate the first occurrence) and one that keeps searching right (to locate the last occurrence). Each search runs in O(log n), giving O(log n) total time and O(1) space. The critical modification is that when nums[mid] == target, you do not return immediately. Instead, you record the index and continue narrowing the search in the appropriate direction.

Why This Problem Matters

Binary search is one of those topics where the gap between "I know the concept" and "I can implement it correctly" is surprisingly wide. Most candidates can write a basic binary search, but when you ask them to find boundaries, off-by-one errors and infinite loops start creeping in. Mastering this problem gives you a reusable pattern for any "find the boundary" binary search variant, which is one of the most common interview patterns at top tech companies.

Understanding the Problem

Let's break down what we're being asked to do:

Given: A sorted array of integers in non-decreasing order and a target value Find: The first and last positions (indices) of the target Return: [-1, -1] if the target is not present Constraint: Must run in O(log n) time

Here's a concrete example with nums = [5, 7, 7, 8, 8, 10] and target = 8:

The target value 8 appears at indices 3 and 4 (highlighted), so we return [3, 4].

A few more examples to solidify the concept:

• searchRange([5, 7, 7, 8, 8, 10], 10) returns [5, 5] since 10 appears only once
• searchRange([5, 7, 7, 8, 8, 10], 6) returns [-1, -1] since 6 is absent
• searchRange([], 4) returns [-1, -1] for an empty array

Edge Cases to Consider

1. Empty array: No elements to search, return [-1, -1]
2. Target not present: Binary search completes without a match
3. Single occurrence: First and last positions are the same index
4. All elements are the target: First = 0, last = length - 1
5. Target at array boundaries: First or last element

Why Standard Binary Search Falls Short

A standard binary search finds any occurrence of the target and returns immediately. That's fine for "does this exist?" questions, but it tells us nothing about where the range of duplicates begins and ends.

Standard binary search lands on index 4 and stops. But the first occurrence is at index 3. We need an approach that keeps searching even after finding a match.

Solution Approach

The key insight is to run two separate binary searches, each with a small but important modification:

1. Find first position: When nums[mid] == target, record the index and move right = mid - 1 to keep searching leftward.
2. Find last position: When nums[mid] == target, record the index and move left = mid + 1 to keep searching rightward.

In both cases, the search continues narrowing until left > right, and the last recorded index is our answer.

Tracing Through: Finding the First Position

Let's walk through finding the first position of 8 in [5, 7, 7, 8, 8, 10]:

Step 1: left=0, right=5, mid=2. nums[2]=7, which is less than 8. Move left to 3.

Step 2: left=3, right=5, mid=4. nums[4]=8, which equals target. Record firstPosition=4, then move right to 3 to keep searching left.

Step 3: left=3, right=3, mid=3. nums[3]=8, which equals target. Update firstPosition=3, then move right to 2. Now left > right, so we stop.

The first position is 3. Notice how the search continued left even after finding 8 at index 4.

Tracing Through: Finding the Last Position

Now let's find the last position of 8:

Step 1: left=0, right=5, mid=2. nums[2]=7, less than 8. Move left to 3.

Step 2: left=3, right=5, mid=4. nums[4]=8, equals target. Record lastPosition=4, move left to 5 to keep searching right.

Step 3: left=5, right=5, mid=5. nums[5]=10, greater than 8. Move right to 4. Now left > right, so we stop.

The last position is 4. Combined result: [3, 4].

Here's the overall flow of the modified binary search for finding the first position:

Implementation

Prefer a different language? Jump to solutions in other languages.

Here's the complete solution in Java:

public class Solution {
  public int[] searchRange(int[] nums, int target) {
    int[] result = {-1, -1};
    result[0] = findFirstPosition(nums, target);
    result[1] = findLastPosition(nums, target);
    return result;
  }

  private int findFirstPosition(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int firstPosition = -1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] == target) {
        firstPosition = mid;
        right = mid - 1;       // Keep searching left
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return firstPosition;
  }

  private int findLastPosition(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int lastPosition = -1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] == target) {
        lastPosition = mid;
        left = mid + 1;        // Keep searching right
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return lastPosition;
  }
}

The two helper methods are nearly identical. The only difference is what happens when nums[mid] == target:

• findFirstPosition moves right left to narrow toward the first match
• findLastPosition moves left right to narrow toward the last match

Complexity Analysis

Time Complexity: O(log n)

Each binary search halves the search space on every iteration, visiting at most O(log n) elements. We run two searches, so the total is 2 * O(log n), which simplifies to O(log n).

Compare this to the naive approach of scanning left and right from any found index, which degrades to O(n) when every element is the target (for example, [8, 8, 8, 8, 8] with target 8).

Space Complexity: O(1)

We use only a fixed number of integer variables (left, right, mid, firstPosition, lastPosition) regardless of input size. No recursion, no auxiliary data structures.

Common Pitfalls

Having seen this problem in hundreds of interviews, here are the mistakes that trip up candidates most often:

1. Returning immediately on match: The whole point of the modification is to keep searching after finding the target. If you return mid when nums[mid] == target, you get a random occurrence instead of the boundary.

2. Off-by-one with pointer updates: When the target is found, you must move right = mid - 1 (not right = mid) for finding the first position, and left = mid + 1 (not left = mid) for finding the last. Using mid instead of mid - 1 or mid + 1 causes infinite loops.

3. Integer overflow in midpoint: Always use mid = left + (right - left) / 2 instead of mid = (left + right) / 2. The latter overflows when left + right exceeds Integer.MAX_VALUE.

4. Forgetting the empty array check: The algorithm handles this naturally since right starts at -1, making left > right immediately. But forgetting to think about this edge case during interviews signals weak problem analysis.

Pro tip: Before coding, trace through the algorithm on paper with a small example like [8, 8] with target 8. This catches most boundary errors before they reach your code.

Interview Tips

When solving this problem in an interview:

1. Start by clarifying: "Should I return 0-indexed positions? What if the array is empty?" These show careful thinking.

2. Explain the O(log n) constraint matters: Mention that a linear scan would work but violates the requirement. This shows you understand why binary search is necessary, not just that it can be applied.

3. Draw the array: Sketch the example on the whiteboard, mark the target positions, and show how each binary search narrows the window differently.

4. Highlight the one-line difference: Point out that findFirstPosition and findLastPosition differ by a single line. This demonstrates clean code design and makes your solution easy to verify.

5. Mention the follow-up: "Once we have first and last positions, counting occurrences is just last - first + 1." Interviewers love this because it shows you're thinking beyond the immediate question.

Key Takeaways

• The standard binary search template needs just one modification to find boundaries: instead of returning on match, record the index and keep narrowing in the target direction.
• Two O(log n) searches give O(log n) total time, which is strictly better than any approach involving a linear scan through the matched range.
• The mid = left + (right - left) / 2 formula prevents integer overflow and is considered best practice for any binary search implementation.
• This "find the boundary" pattern transfers directly to problems like finding the insertion point, counting occurrences, and searching in rotated arrays.
• Always trace through a small example (two or three elements) before coding. Binary search off-by-one errors are notoriously hard to debug in your head.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def search_range(self, nums: List[int], target: int) -> List[int]:
        def find_leftmost(nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        def find_rightmost(nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right

        left_index = find_leftmost(nums, target)
        right_index = find_rightmost(nums, target)

        if left_index <= right_index and right_index < len(nums) and nums[left_index] == target and nums[right_index] == target:
            return [left_index, right_index]
        else:
            return [-1, -1]

The Python solution uses a slightly different approach: find_leftmost finds the insertion point (the first index where nums[mid] ≥ target) and find_rightmost finds the last index where nums[mid] ≤ target. A final bounds check confirms the target actually exists.

JavaScript

class Solution {
  searchRange(nums, target) {
    const findFirst = (nums, target) => {
      let left = 0;
      let right = nums.length - 1;
      let first = -1;
      while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
          first = mid;
          right = mid - 1;
        } else if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return first;
    };

    const findLast = (nums, target) => {
      let left = 0;
      let right = nums.length - 1;
      let last = -1;
      while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (nums[mid] === target) {
          last = mid;
          left = mid + 1;
        } else if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return last;
    };

    const first = findFirst(nums, target);
    if (first === -1) {
      return [-1, -1];
    }
    const last = findLast(nums, target);
    return [first, last];
  }
}

TypeScript

class Solution {
  searchRange(nums: number[], target: number): number[] {
    const findFirst = (nums: number[], target: number): number => {
      let left = 0;
      let right = nums.length - 1;
      let first = -1;
      while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
          first = mid;
          right = mid - 1;
        } else if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return first;
    };

    const findLast = (nums: number[], target: number): number => {
      let left = 0;
      let right = nums.length - 1;
      let last = -1;
      while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
          last = mid;
          left = mid + 1;
        } else if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return last;
    };

    const first = findFirst(nums, target);
    if (first === -1) {
      return [-1, -1];
    }
    const last = findLast(nums, target);
    return [first, last];
  }
}

C++

#include <vector>

class Solution {
public:
    std::vector<int> searchRange(std::vector<int> &nums, int target) {
        std::vector<int> result = {-1, -1};
        result[0] = findFirstPosition(nums, target);
        result[1] = findLastPosition(nums, target);
        return result;
    }

private:
    int findFirstPosition(std::vector<int> &nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;
        int firstPosition = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                firstPosition = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return firstPosition;
    }

    int findLastPosition(std::vector<int> &nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;
        int lastPosition = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                lastPosition = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return lastPosition;
    }
};

Scala

class Solution {
  def searchRange(nums: Array[Int], target: Int): Array[Int] = {
    def findBound(isFirst: Boolean): Int = {
      var left = 0
      var right = nums.length - 1
      var bound = -1

      while (left <= right) {
        val mid = left + (right - left) / 2
        if (nums(mid) == target) {
          bound = mid
          if (isFirst) right = mid - 1
          else left = mid + 1
        } else if (nums(mid) < target) {
          left = mid + 1
        } else {
          right = mid - 1
        }
      }
      bound
    }

    val firstPos = findBound(isFirst = true)
    if (firstPos == -1) Array(-1, -1)
    else Array(firstPos, findBound(isFirst = false))
  }
}

The Scala solution uses a single findBound function with an isFirst parameter to toggle the search direction, reducing code duplication.

Kotlin

class Solution {
  fun searchRange(nums: IntArray, target: Int): IntArray {
    val result = intArrayOf(-1, -1)
    result[0] = findFirstPosition(nums, target)
    result[1] = findLastPosition(nums, target)
    return result
  }

  private fun findFirstPosition(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    var firstPosition = -1
    while (left <= right) {
      val mid = left + (right - left) / 2
      if (nums[mid] == target) {
        firstPosition = mid
        right = mid - 1
      } else if (nums[mid] < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
    return firstPosition
  }

  private fun findLastPosition(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    var lastPosition = -1
    while (left <= right) {
      val mid = left + (right - left) / 2
      if (nums[mid] == target) {
        lastPosition = mid
        left = mid + 1
      } else if (nums[mid] < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
    return lastPosition
  }
}

Swift

class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        var result = [-1, -1]
        result[0] = findFirstPosition(nums, target)
        result[1] = findLastPosition(nums, target)
        return result
    }

    private func findFirstPosition(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var firstPosition = -1
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] == target {
                firstPosition = mid
                right = mid - 1
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return firstPosition
    }

    private func findLastPosition(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var lastPosition = -1
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] == target {
                lastPosition = mid
                left = mid + 1
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return lastPosition
    }
}

Rust

impl Solution {
    pub fn search_range(&self, nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut result = vec![-1, -1];
        result[0] = self.find_first_position(&nums, target);
        result[1] = self.find_last_position(&nums, target);
        result
    }

    fn find_first_position(&self, nums: &[i32], target: i32) -> i32 {
        let mut left: i32 = 0;
        let mut right: i32 = nums.len() as i32 - 1;
        let mut first_position: i32 = -1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] == target {
                first_position = mid;
                right = mid - 1;
            } else if nums[mid as usize] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        first_position
    }

    fn find_last_position(&self, nums: &[i32], target: i32) -> i32 {
        let mut left: i32 = 0;
        let mut right: i32 = nums.len() as i32 - 1;
        let mut last_position: i32 = -1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] == target {
                last_position = mid;
                left = mid + 1;
            } else if nums[mid as usize] < target {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        last_position
    }
}

C#

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = FindFirstPosition(nums, target);
        result[1] = FindLastPosition(nums, target);
        return result;
    }

    private int FindFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;
        int firstPosition = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                firstPosition = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return firstPosition;
    }

    private int FindLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;
        int lastPosition = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                lastPosition = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return lastPosition;
    }
}

Dart

class Solution {
  List<int> searchRange(List<int> nums, int target) {
    List<int> result = [-1, -1];
    result[0] = _findFirstPosition(nums, target);
    result[1] = _findLastPosition(nums, target);
    return result;
  }

  int _findFirstPosition(List<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int firstPosition = -1;
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      if (nums[mid] == target) {
        firstPosition = mid;
        right = mid - 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return firstPosition;
  }

  int _findLastPosition(List<int> nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int lastPosition = -1;
    while (left <= right) {
      int mid = left + (right - left) ~/ 2;
      if (nums[mid] == target) {
        lastPosition = mid;
        left = mid + 1;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return lastPosition;
  }
}

Ruby

class Solution
  def search_range(nums, target)
    find_leftmost = lambda do |nums, target|
      left, right = 0, nums.length - 1
      while left <= right
        mid = left + (right - left) / 2
        if nums[mid] < target
          left = mid + 1
        else
          right = mid - 1
        end
      end
      left
    end

    find_rightmost = lambda do |nums, target|
      left, right = 0, nums.length - 1
      while left <= right
        mid = left + (right - left) / 2
        if nums[mid] <= target
          left = mid + 1
        else
          right = mid - 1
        end
      end
      right
    end

    left_index = find_leftmost.call(nums, target)
    right_index = find_rightmost.call(nums, target)

    if left_index <= right_index && right_index < nums.length && nums[left_index] == target && nums[right_index] == target
      [left_index, right_index]
    else
      [-1, -1]
    end
  end
end

PHP

class Solution {
    public function searchRange(array $nums, int $target): array {
        $result = [-1, -1];
        $result[0] = $this->findFirstPosition($nums, $target);
        $result[1] = $this->findLastPosition($nums, $target);
        return $result;
    }

    private function findFirstPosition(array $nums, int $target): int {
        $left = 0;
        $right = count($nums) - 1;
        $firstPosition = -1;
        while ($left <= $right) {
            $mid = $left + intdiv($right - $left, 2);
            if ($nums[$mid] === $target) {
                $firstPosition = $mid;
                $right = $mid - 1;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        return $firstPosition;
    }

    private function findLastPosition(array $nums, int $target): int {
        $left = 0;
        $right = count($nums) - 1;
        $lastPosition = -1;
        while ($left <= $right) {
            $mid = $left + intdiv($right - $left, 2);
            if ($nums[$mid] === $target) {
                $lastPosition = $mid;
                $left = $mid + 1;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        return $lastPosition;
    }
}

Practice Makes Perfect

Once you've nailed this "find the boundary" binary search pattern, try these related problems to deepen your understanding:

• Search Insert Position (finding where an element would go in a sorted array)
• Search in Rotated Sorted Array (binary search with an added twist)
• Find Minimum in Rotated Sorted Array (boundary search in a different context)
• Count of Range Sum (applying boundary concepts to more complex queries)

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or targeting your dream role at a FAANG company, mastering binary search patterns like this one will set you apart.