34. Find First and Last Position of Element in Sorted Array #

Problem #

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

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]

Problem Summary #

Given an integer array nums sorted in ascending order, and a target value target. Find the starting position and ending position of the given target value in the array. Your algorithm’s time complexity must be O(log n). If the target value does not exist in the array, return [-1, -1].

Solution Approach #

Given a sorted array nums and a number target, find the index of the first element in the array that is equal to this element, and the index of the last element that is equal to this element.
This problem is a classic variant of binary search. Binary search has 4 basic variants:
1. Find the first element whose value equals the given value
2. Find the last element whose value equals the given value
3. Find the first element whose value is greater than or equal to the given value
4. Find the last element whose value is less than or equal to the given value
The solution approach for this problem can use the methods of variant 1 and variant 2 respectively to solve it. Or use the method of variant 1 once, and then loop backward to find the last element equal to the given value. However, the latter method may reduce the time complexity to O(n), because it is possible that all n elements in the array are the same as the given element. (The implementations of the 4 basic variants are shown in the code)

Code #


package leetcode

func searchRange(nums []int, target int) []int {
	return []int{searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)}

}

// Binary search for the first element equal to target, time complexity O(logn)
func searchFirstEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == 0) || (nums[mid-1] != target) { // Found the first element equal to target
				return mid
			}
			high = mid - 1
		}
	}
	return -1
}

// Binary search for the last element equal to target, time complexity O(logn)
func searchLastEqualElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] > target {
			high = mid - 1
		} else if nums[mid] < target {
			low = mid + 1
		} else {
			if (mid == len(nums)-1) || (nums[mid+1] != target) { // Found the last element equal to target
				return mid
			}
			low = mid + 1
		}
	}
	return -1
}

// Binary search for the first element greater than or equal to target, time complexity O(logn)
func searchFirstGreaterElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] >= target {
			if (mid == 0) || (nums[mid-1] < target) { // Found the first element greater than or equal to target
				return mid
			}
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return -1
}

// Binary search for the last element less than or equal to target, time complexity O(logn)
func searchLastLessElement(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + ((high - low) >> 1)
		if nums[mid] <= target {
			if (mid == len(nums)-1) || (nums[mid+1] > target) { // Found the last element less than or equal to target
				return mid
			}
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return -1
}