LeetCode 034 Find First and Last Position of Element in Sorted Array

LeetCode

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.

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]

Constraints:

0 <= nums.length <= 10<sup>5</sup> -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
nums is a non-decreasing array. -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

求有序数列中元素等于target的第一个和最后一个下标

解题思路：

用模板

解题步骤：

N/A

注意事项：

1. 数组为空的情况要返回-1

Python代码：

def searchRange(self, nums: List[int], target: int) -> List[int]:
	first = self.first_position(nums, target)
	last = self.last_position(nums, target)
	return [first, last]

def last_position(self, nums, target):
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			start = mid
	if nums[end] == target:
		return end
	if nums[start] == target:
		return start
	return -1

def first_position(self, nums, target):
	if not nums:
		return -1
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start+ (end - start) // 2
		if target < nums[mid]:
			end = mid
		elif target > nums[mid]:
			start = mid
		else:
			end = mid
	if nums[start] == target:
		return start
	if nums[end] == target:
		return end
	return -1

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)