LeetCode 34: Find First and Last Position of Element in Sorted Array (Dual Binary Search Boundaries)

2026-03-19 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 34Binary SearchArrayBoundary

Today we solve LeetCode 34 - Find First and Last Position of Element in Sorted Array.

Source: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

English

Problem Summary

Given a sorted integer array nums and a target, return the first and last index of the target. If target does not exist, return [-1, -1]. Required time complexity is O(log n).

Key Insight

Run binary search twice with different boundary bias:

- Left boundary: find first index where nums[i] >= target.
- Right boundary: find first index where nums[i] > target, then minus one.

Brute Force and Limitations

Linear scan can find the segment in O(n), but violates the logarithmic requirement and is inefficient for large arrays.

Optimal Algorithm Steps

1) Binary search lower bound for target.
2) If lower bound is out of range or value != target, return [-1, -1].
3) Binary search lower bound for target + 1 (or upper bound for target).
4) Right index = returned position - 1.

Complexity Analysis

Time: O(log n) (two binary searches).
Space: O(1).

Common Pitfalls

- Forgetting empty array case.
- Mixing inclusive/exclusive intervals incorrectly.
- Forgetting to validate that left boundary truly points to target.
- Overflow-prone midpoint formula in some languages.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums, target);
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        int right = lowerBound(nums, target + 1) - 1;
        return new int[]{left, right};
    }

    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

func searchRange(nums []int, target int) []int {
    left := lowerBound(nums, target)
    if left == len(nums) || nums[left] != target {
        return []int{-1, -1}
    }
    right := lowerBound(nums, target+1) - 1
    return []int{left, right}
}

func lowerBound(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := l + (r-l)/2
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        if (left == (int)nums.size() || nums[left] != target) return {-1, -1};
        int right = lowerBound(nums, target + 1) - 1;
        return {left, right};
    }

private:
    int lowerBound(const vector<int>& nums, int target) {
        int l = 0, r = (int)nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        left = self.lower_bound(nums, target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        right = self.lower_bound(nums, target + 1) - 1
        return [left, right]

    def lower_bound(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l

var searchRange = function(nums, target) {
  const left = lowerBound(nums, target);
  if (left === nums.length || nums[left] !== target) {
    return [-1, -1];
  }
  const right = lowerBound(nums, target + 1) - 1;
  return [left, right];
};

function lowerBound(nums, target) {
  let l = 0, r = nums.length;
  while (l < r) {
    const mid = l + ((r - l) >> 1);
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

中文

题目概述

给定一个升序数组 nums 和目标值 target，返回目标值的起始与结束下标；若不存在返回 [-1, -1]。要求时间复杂度为 O(log n)。

核心思路

把“找区间”拆成两次“找边界”的二分：

- 左边界：第一个 >= target 的位置。
- 右边界：第一个 > target 的位置减一。

暴力解法与不足

线性扫描能找到区间，但复杂度是 O(n)，不满足题目对对数复杂度的要求。

最优算法步骤

1）先二分出 target 的 lower bound。
2）若越界或该位置不等于 target，直接返回 [-1, -1]。
3）再二分出 target+1 的 lower bound（等价于 target 的 upper bound）。
4）右端点为该位置减一。

复杂度分析

时间复杂度：O(log n)（两次二分）。
空间复杂度：O(1)。

常见陷阱

- 忽略空数组。
- 左闭右开与左闭右闭区间写法混用。
- 没有校验左边界是否真的命中 target。
- 中点计算在某些语言中的潜在溢出问题。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums, target);
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        int right = lowerBound(nums, target + 1) - 1;
        return new int[]{left, right};
    }

    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}

func searchRange(nums []int, target int) []int {
    left := lowerBound(nums, target)
    if left == len(nums) || nums[left] != target {
        return []int{-1, -1}
    }
    right := lowerBound(nums, target+1) - 1
    return []int{left, right}
}

func lowerBound(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := l + (r-l)/2
        if nums[mid] >= target {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        if (left == (int)nums.size() || nums[left] != target) return {-1, -1};
        int right = lowerBound(nums, target + 1) - 1;
        return {left, right};
    }

private:
    int lowerBound(const vector<int>& nums, int target) {
        int l = 0, r = (int)nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        left = self.lower_bound(nums, target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        right = self.lower_bound(nums, target + 1) - 1
        return [left, right]

    def lower_bound(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        return l

var searchRange = function(nums, target) {
  const left = lowerBound(nums, target);
  if (left === nums.length || nums[left] !== target) {
    return [-1, -1];
  }
  const right = lowerBound(nums, target + 1) - 1;
  return [left, right];
};

function lowerBound(nums, target) {
  let l = 0, r = nums.length;
  while (l < r) {
    const mid = l + ((r - l) >> 1);
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}