Backend interview prep

Start

First and Last Position of Element in Sorted Array - Java Coding Interview Guide

Learn how to find the first and last position of an element in a sorted array using Binary Search in Java with explanation, dry run, optimized solution, production use cases, interview questions, and best practices.

First and Last Position of Element in Sorted Array

Java Coding Interview Track

Binary Search — Lesson 03

Ordered Lessons

# Lesson
01 Binary Search
02 Search Insert Position
03 First and Last Position ←
04 Find Peak Element
05 Search Rotated Array
06 Binary Search Interview

Problem Statement

Given a sorted array of integers, return the first and last positions of a target value.

If the target does not exist, return:

[-1, -1]

The solution must run in O(log n) time.

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]

Understanding the Problem

Index

0 1 2 3 4 5

Array

5 7 7 8 8 10

Target = 8

Need to return

First = 3

Last = 4

A normal Binary Search stops when it finds one occurrence.

This problem requires finding both boundaries.

Brute Force Solution

Traverse the array.

  • Find first occurrence.
  • Continue until the last occurrence.

Complexity

Time

O(n)

Space

O(1)

Optimal Solution

Use Binary Search twice.

  1. Find First Occurrence.
  2. Find Last Occurrence.

Overall complexity remains:

O(log n)

Binary Search Logic

First Occurrence

Whenever target is found:

  • Save answer.
  • Continue searching on the left side.

Last Occurrence

Whenever target is found:

  • Save answer.
  • Continue searching on the right side.

Visualization

graph TD
    Array["Array"] --> N_5_7_7_8_8_10["5 7 7 8 8 10"]
    N_5_7_7_8_8_10["5 7 7 8 8 10"] --> N_["↑"]
    N_["↑"] --> First["First"]
    First["First"] --> Continue_Left["Continue Left"]
    Continue_Left["Continue Left"] --> Found["Found"]
    Found["Found"] --> N_1["----------------------"]
    N_1["----------------------"] --> Array["Array"]
    Array["Array"] --> N_5_7_7_8_8_10["5 7 7 8 8 10"]
    N_5_7_7_8_8_10["5 7 7 8 8 10"] --> N_["↑"]
    N_["↑"] --> Last["Last"]
    Last["Last"] --> Continue_Right["Continue Right"]

Algorithm

graph TD
    Find_First["Find First"] --> Binary_Search["Binary Search"]
    Binary_Search["Binary Search"] --> Found["Found?"]
    Found["Found?"] --> Store_Index["Store Index"]
    Store_Index["Store Index"] --> Move_Left["Move Left"]
    Move_Left["Move Left"] --> Return_First["Return First"]
    Return_First["Return First"] --> N_["--------------------"]
    N_["--------------------"] --> Find_Last["Find Last"]
    Find_Last["Find Last"] --> Binary_Search["Binary Search"]
    Binary_Search["Binary Search"] --> Found["Found?"]
    Found["Found?"] --> Store_Index["Store Index"]
    Store_Index["Store Index"] --> Move_Right["Move Right"]
    Move_Right["Move Right"] --> Return_Last["Return Last"]

Dry Run

nums

5 7 7 8 8 10

target = 8

mid = 2

7 < 8

Move Right

mid = 4

Found

Answer = 4

Search Left

mid = 3

Found

Answer = 3

Search Left

End

First = 3

mid = 4

Found

Answer = 4

Search Right

End

Last = 4

Java Solution

public class FirstLastPosition {

    public static int[] searchRange(int[] nums, int target) {

        return new int[]{
                firstOccurrence(nums, target),
                lastOccurrence(nums, target)
        };

    }

    private static int firstOccurrence(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        int answer = -1;

        while (left <= right) {

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

            if (nums[mid] == target) {
                answer = mid;
                right = mid - 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return answer;

    }

    private static int lastOccurrence(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;
        int answer = -1;

        while (left <= right) {

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

            if (nums[mid] == target) {
                answer = mid;
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return answer;

    }

    public static void main(String[] args) {

        int[] nums = {5,7,7,8,8,10};

        int[] result = searchRange(nums, 8);

        System.out.println(result[0] + ", " + result[1]);

    }

}

Complexity Analysis

Operation Complexity
Time O(log n)
Space O(1)

Why Two Binary Searches?

A standard Binary Search stops immediately after finding the target.

To locate:

  • First occurrence → continue searching left.
  • Last occurrence → continue searching right.

This guarantees logarithmic complexity.

Production Use Cases

Search Engines

Find all matching indexed documents.

Database Indexes

Locate the range of duplicate keys in B-Tree indexes.

E-Commerce

Find all products with the same rating or price.

Log Analysis

Find all logs generated at the same timestamp.

Banking Systems

Retrieve transactions matching a specific account or amount.

Analytics Platforms

Determine the range of identical metrics in sorted datasets.

Common Mistakes

It returns only one occurrence.

Stopping After Finding Target

Must continue searching toward the boundary.

Moving Wrong Pointer

For first occurrence:

right = mid - 1;

For last occurrence:

left = mid + 1;

Forgetting Default Value

Initialize

int answer = -1;

Interview Tips

Always explain:

  • Why one Binary Search is not enough.
  • Difference between first and last occurrence.
  • Why complexity remains O(log n).
  • This problem is the foundation of Lower Bound and Upper Bound algorithms.

Related Problems

  • Binary Search
  • Lower Bound
  • Upper Bound
  • Search Insert Position
  • Count Occurrences
  • Floor and Ceil
  • Search in Rotated Array

Interview Questions

1. Why can't a normal Binary Search solve this problem?

Answer

A standard Binary Search returns any matching index and stops immediately. It does not guarantee the first or last occurrence.

2. Why do we perform Binary Search twice?

Answer

One search finds the left boundary (first occurrence), and the second finds the right boundary (last occurrence).

3. What is the time complexity?

Answer

Each Binary Search takes O(log n), so the total complexity is still O(log n).

4. What is the space complexity?

Answer

O(1) because the iterative solution uses constant extra space.

5. What happens if the target is not present?

Answer

Both searches return -1, resulting in [-1, -1].

6. How is the first occurrence found?

Answer

Whenever the target is found, store the index and continue searching the left half.

7. How is the last occurrence found?

Answer

Whenever the target is found, store the index and continue searching the right half.

Answer

Yes. Standard Binary Search returns any occurrence. Modified Binary Search is required to locate the boundaries.

9. Where is this technique used in production?

Answer

Database indexes, search engines, analytics systems, financial transaction searches, and reporting applications.

Answer

Lower Bound, Upper Bound, Search Insert Position, Count Occurrences, Floor and Ceil, and Search Range.

Quick Revision

Concept Value
Pattern Modified Binary Search
Searches Required 2
Time Complexity O(log n)
Space Complexity O(1)
Handles Duplicates Yes
First Occurrence Search Left
Last Occurrence Search Right
Interview Frequency ⭐⭐⭐⭐⭐

Key Takeaways

  • This problem is solved by performing two modified Binary Searches.
  • Continue searching left to find the first occurrence and right to find the last occurrence.
  • The overall complexity remains O(log n) despite running Binary Search twice.
  • This pattern is widely used in database indexing, analytics, and search systems.
  • Mastering this problem makes advanced Binary Search concepts like Lower Bound, Upper Bound, and Count Occurrences much easier.