Binary SearchMediumO(log n) time · O(1) space

First and Last Position

Mahabharata — The Front and Rear of the Same Clan — Finding Where a Warrior's Line Begins and Ends

एकस्य कुलस्य प्रथमः कः? अन्तिमः कः?। व्यवस्थिते सैन्ये — द्विः खोजित्वा उत्तरम् ज्ञातव्यम्॥

*For one clan — who stands first? Who stands last? In the sorted army — search twice to find both answers.*

The Story

Given a sorted array of integers and a target, return `[first_index, last_index]` where the target occurs. Return `[-1, -1]` if not found.

For `nums = [5,7,7,8,8,10]`, target=8: return `[3,4]`. For `nums = [5,7,7,8,8,10]`, target=6: return `[-1,-1]`.

Two clans of warriors, both named "8", stood in the formation. The general needed the first and last of their kind.

**Two binary searches:**

**Finding the FIRST occurrence:** Same as bs-2 ceiling, but for exact match: - When arr[mid] == target: save result, search LEFT (look for earlier occurrence) - When arr[mid] < target: left = mid+1 - When arr[mid] > target: right = mid-1

**Finding the LAST occurrence:** - When arr[mid] == target: save result, search RIGHT (look for later occurrence) - When arr[mid] < target: left = mid+1 - When arr[mid] > target: right = mid-1

Combined as two calls using a `lower` and `upper` binary search: - `lower(target)` = first index where nums[i] >= target - `upper(target)` = first index where nums[i] > target - Answer = `[lower, upper-1]` - If lower > upper-1 or nums[lower] ≠ target: return [-1,-1]

Trace `[5,7,7,8,8,10]`, target=8:

First search: l=0,r=5,mid=2(7)<8→l=3. l=3,r=5,mid=4(8)==8→save=4,r=3. l=3,r=3,mid=3(8)==8→save=3,r=2. l=3>r=2. First=3.

Last search: l=0,r=5,mid=2(7)<8→l=3. l=3,r=5,mid=4(8)==8→save=4,l=5. l=5,r=5,mid=5(10)>8→r=4. l=5>r=4. Last=4.

Return [3,4] ✓

The Linear Range Finder

Scan from left for first occurrence, from right for last. O(n).

java

public int[] searchRangeBruteForce(int[] nums, int target) {
    int first = -1, last = -1;
    for (int i = 0; i < nums.length; i++)
        if (nums[i] == target) { if (first==-1) first=i; last=i; }
    return new int[]{first, last};
}

The Dual Binary Search Wisdom

First occurrence: when arr[mid]==target, save and go LEFT. Last occurrence: when arr[mid]==target, save and go RIGHT. Two separate binary searches, O(log n) each.

java

public int[] searchRange(int[] nums, int target) {
    return new int[]{findFirst(nums, target), findLast(nums, target)};
}

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

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

Step-by-Step Walkthrough

[8,8,8], target=8
findFirst: l=0,r=2,mid=1==8→save=1,r=0. l=0,r=0,mid=0==8→save=0,r=-1. Return 0.
findLast: l=0,r=2,mid=1==8→save=1,l=2. l=2,r=2,mid=2==8→save=2,l=3. Return 2.
Return [0,2] ✅

Deep Insight

**The save-and-continue direction determines first/last:** - Save + go LEFT → find FIRST occurrence - Save + go RIGHT → find LAST occurrence

Same structure as bs-2 (ceiling uses save+go-left), just with exact match instead of >=.

**lower_bound/upper_bound combination:** An elegant alternative: ```java int first = lowerBound(nums, target); // First index where nums[i] >= target int last = lowerBound(nums, target+1) - 1; // First index where nums[i] > target, minus 1 if (first < nums.length && nums[first] == target) return [first, last]; return [-1, -1]; ```

**Template validity:** The exact same `findFirst`/`findLast` functions work for any sorted array problem asking for ranges of equal elements.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(1)	Linear scan
Optimal	O(log n)	O(1)	Two binary searches, each O(log n)

Pattern Recognition

✅ Find range of target in sorted array
✅ findFirst: match → save+right=mid-1
✅ findLast: match → save+left=mid+1
✅ Two separate binary searches

**LeetCode Trigger Phrases:**
→ "find first and last position of element in sorted array"
→ "range of target in sorted array"
→ Any first/last occurrence binary search

Bhagavad Gita 2.28

अव्यक्तादीनि भूतानि व्यक्तमध्यानि भारत। अव्यक्तनिधनान्येव तत्र का परिदेवना॥

All created beings are unmanifest in their beginning, manifest in their interim state, and unmanifest again at their end. What is there to grieve about?

Connection: The algorithm searches for the first emergence (beginning) and last disappearance (end) of the target in the array — the manifest range of its existence within the sorted sequence. Like the Gita's teaching that all beings have a beginning, a manifest middle, and an end, the target's occurrences have a first and last position. Binary search finds both with precise efficiency, honoring both the arrival and departure of each value in the array's ordered story.