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

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.
  • ⏰ 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:

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)