Find first and last positions of target element in sorted array

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.

Examples

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]

Similar problem

[Count frequency of target element in sorted array](count-frequency-of-target-element-in-sorted-array)

Solution

Method 1 - Brute Force

The Naive Approach is to run a for loop and check given elements in array.

1. Iterate through the array with a for loop from i = 0 to n-1.
2. Initialize first and last to -1.
3. When the element is found for the first time, set first to i.
4. Update last to i each time the element is found.
5. Print first and last.

Complexity

• ⏰ Time complexity: O(n), where n is number of elements in array.
• 🧺 Space complexity: O(1)

Method 2 - Using Binary Search to Find First and Last Separately

We have already solved 2 problems:

• [Find first position of target element in sorted array](find-first-position-of-target-element-in-sorted-array)
• [Find last position of target element in sorted array](find-last-position-of-target-element-in-sorted-array)

Then, we can just call respective methods, and return the position.

Code

Java

public int[] searchRange(int[] nums, int target) {
	int[] result = new int[2];
	result[0] = searchFirstIterative(nums, target);
	result[1] = searchLastIterative(nums, target);
	return result;
}

Complexity

• ⏰ Time complexity: O(log n)
• 🧺 Space complexity: O(1)