⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#34) before relying on it.

🔎 Find First and Last Position

An interactive visualization of how two binary searches find the leftmost and rightmost positions of a target in a sorted array. Watch each phase narrow down the search space step by step.

Binary Search LeetCode 34 ↗ Medium

The Problem

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.

Interactive Visualization

Array (comma-separated)

Target

Preset

Speed:

Array

Current Step

Press Step or Play to begin.

Code

fun searchRange(nums: IntArray, target: Int): IntArray {    fun findLeft(nums: IntArray, target: Int): Int {        var lo = 0; var hi = nums.size - 1        var idx = -1        while (lo <= hi) {            val mid = (lo + hi) / 2            if (nums[mid] == target) {                idx = mid                hi = mid - 1  // keep searching left            } else if (nums[mid] < target) {                lo = mid + 1            } else {                hi = mid - 1            }        }        return idx    }    fun findRight(nums: IntArray, target: Int): Int {        var lo = 0; var hi = nums.size - 1        var idx = -1        while (lo <= hi) {            val mid = (lo + hi) / 2            if (nums[mid] == target) {                idx = mid                lo = mid + 1  // keep searching right            } else if (nums[mid] < target) {                lo = mid + 1            } else {                hi = mid - 1            }        }        return idx    }    return intArrayOf(findLeft(nums, target),        findRight(nums, target))}

def searchRange(nums, target):    def findLeft(nums, target):        lo, hi = 0, len(nums) - 1        idx = -1        while lo <= hi:            mid = (lo + hi) // 2            if nums[mid] == target:                idx = mid                hi = mid - 1  # keep searching left            elif nums[mid] < target:                lo = mid + 1            else:                hi = mid - 1        return idx    def findRight(nums, target):        lo, hi = 0, len(nums) - 1        idx = -1        while lo <= hi:            mid = (lo + hi) // 2            if nums[mid] == target:                idx = mid                lo = mid + 1  # keep searching right            elif nums[mid] < target:                lo = mid + 1            else:                hi = mid - 1        return idx    return [findLeft(nums, target),            findRight(nums, target)]

How It Works

Key Insight

A standard binary search finds any occurrence of the target, but we need the first and last positions. The trick is to run two modified binary searches: one that keeps searching left after finding the target (to find the leftmost occurrence), and one that keeps searching right (to find the rightmost occurrence).

The Algorithm

Phase 1 — findLeft: When nums[mid] == target, record mid as a candidate and set hi = mid - 1 to continue searching in the left half for an earlier occurrence.
Phase 2 — findRight: When nums[mid] == target, record mid as a candidate and set lo = mid + 1 to continue searching in the right half for a later occurrence.
In both phases, if nums[mid] < target, move lo = mid + 1. If nums[mid] > target, move hi = mid - 1.
Each phase returns the last recorded candidate index, or -1 if the target was never found.

Complexity

Time O(log n)

Space O(1)

Two binary searches each run in O(log n), so the total time is O(log n). Only a constant number of variables are used, giving O(1) space.