Loading problems...
TL;DR: To solve this in logarithmic time, perform two modified binary searches: one to locate the leftmost index of the target and another to locate the rightmost index.
The problem asks us to find the starting and ending indices of a specific target value within an array of integers sorted in non-decreasing order. If the target does not exist in the array, we must return [-1, -1]. This is the core challenge of LeetCode 34: Find First and Last Position of Element in Sorted Array, a classic interview question that tests the ability to modify standard search algorithms.
The critical constraint is that the algorithm must run in O(log n) time complexity. This immediately rules out linear scanning approaches.
The naive approach involves iterating through the array linearly to find the target.
first and last to -1.0 to n-1.target, set first to the current index.target, update last to the current index (since the array is sorted, subsequent occurrences are always to the right).[first, last].Pseudo-code:
textfunction bruteForce(nums, target): first = -1 last = -1 for i from 0 to length(nums) - 1: if nums[i] == target: if first == -1: first = i last = i return [first, last]
Time Complexity Analysis: The time complexity is O(n), where n is the number of elements in the array. In the worst case, we must traverse the entire array.
Why it fails: While this solution produces the correct output, it violates the explicit problem constraint requiring O(log n) runtime complexity. In a large dataset (up to elements), an O(n) solution is significantly slower than O(log n), and in an interview context, this solution would be considered suboptimal.
The standard binary search algorithm returns the index of any occurrence of the target. However, it does not guarantee finding the first or last occurrence when duplicates exist.
To solve LeetCode 34 efficiently, we must recognize that finding the "first" position and the "last" position are two separate sub-problems that can be solved using the same logic with a slight variation.
The Key Invariant:
When we find nums[mid] == target, we have found an instance of the target, but we do not stop.
mid as a potential answer but assume the true first position might lie to the left. Therefore, we narrow the search space to [low, mid - 1].mid as a potential answer but assume the true last position might lie to the right. Therefore, we narrow the search space to [mid + 1, high].Visual Description: Imagine the array as a series of blocks. The binary search repeatedly cuts the search space in half.
low and high pointers cross, ensuring the boundary has been identified precisely.
Let's trace the algorithm with nums = [5, 7, 7, 8, 8, 10] and target = 8.
Pass 1: Find First Position
low=0, high=5, mid=2. nums[2] is 7. , so low becomes 3.low=3, high=5, mid=4. nums[4] is 8.
index = 4.high becomes 3.low=3, high=3, mid=3. nums[3] is 8.
index = 3.high becomes 2.low=3, high=2. Loop terminates. First Position = 3.Pass 2: Find Last Position
low=0, high=5, mid=2. nums[2] is 7. , so low becomes 3.low=3, high=5, mid=4. nums[4] is 8.
index = 4.low becomes 5.low=5, high=5, mid=5. nums[5] is 10. , so high becomes 4.low=5, high=4. Loop terminates. Last Position = 4.Result: [3, 4].
The correctness relies on the monotonicity of the sorted array.
while (low <= high) loop is guaranteed to terminate because the search space reduces by roughly half in each iteration, eventually causing pointers to cross.nums[mid] == target will eventually be true.high to mid - 1 after a match (when finding the first), we ensure that we never settle for a non-minimal index. We exhaustively verify that no target exists to the left of the current candidate. The symmetric logic applies to finding the last index.cppclass Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> result = {-1, -1}; result[0] = findBound(nums, target, true); // Find first if (result[0] == -1) return result; // Target not found result[1] = findBound(nums, target, false); // Find last return result; } private: int findBound(vector<int>& nums, int target, bool isFirst) { int left = 0, right = nums.size() - 1; int boundIndex = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { boundIndex = mid; // If finding first, narrow search to left half if (isFirst) { right = mid - 1; } // If finding last, narrow search to right half else { left = mid + 1; } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return boundIndex; } };
javaclass Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[]{-1, -1}; result[0] = findBound(nums, target, true); // If the target isn't found once, it won't be found twice if (result[0] == -1) { return result; } result[1] = findBound(nums, target, false); return result; } private int findBound(int[] nums, int target, boolean isFirst) { int left = 0; int right = nums.length - 1; int index = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { index = mid; if (isFirst) { right = mid - 1; // Continue searching left } else { left = mid + 1; // Continue searching right } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return index; } }
pythonclass Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: def find_bound(is_first: bool) -> int: left, right = 0, len(nums) - 1 bound_index = -1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: bound_index = mid if is_first: right = mid - 1 # Narrow search to left else: left = mid + 1 # Narrow search to right elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return bound_index start = find_bound(True) if start == -1: return [-1, -1] end = find_bound(False) return [start, end]
Time Complexity: We perform two separate binary searches. Each binary search operates on an array of size and takes logarithmic time. The total time is , which simplifies to .
Space Complexity:
The algorithm uses a constant amount of extra space for pointers (low, high, mid) and temporary variables. No auxiliary data structures are used.
The Binary Search - Find First/Last Occurrence pattern logic is directly applicable to several other problems. Understanding how to continue searching after a match is key to solving:
Q: Why does my solution get a Time Limit Exceeded (TLE) error?
Mistake: Not updating low or high correctly inside the loop, leading to an infinite loop.
Explanation: A common conceptual gap is setting low = mid or high = mid without conditions that guarantee the range shrinks.
Consequence: The pointers get stuck on adjacent elements, and the loop never terminates. Always use mid + 1 or mid - 1.
Q: Why does my code return a random index of the target, not the first or last?
Mistake: Returning mid immediately upon finding nums[mid] == target.
Explanation: Standard binary search returns the index of the first match it encounters. This match could be in the middle of a sequence of duplicates.
Consequence: Correctness failure. You must update a candidate variable and searching in the appropriate direction.
Q: Can I use a linear scan after finding the first match?
Mistake: Finding one instance via binary search, then expanding outwards linearly (e.g., while nums[i] == target: i++).
Explanation: While this works for small duplicate counts, the problem constraints allow for cases where the array consists entirely of the target value (e.g., copies of '8').
Consequence: Efficiency failure. The worst-case complexity degrades to , violating the strict requirement.