LeetCode-34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]
。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
解题思路:看到排序数组的查找首先想到二分查找,其时间复杂度为logn。在查找元素的第一个位置时,判断条件为if nums[mid] >= target: right = mid -1;在查找元素的最后一个位置时,判断条件为if nums[mid] > target: right = mid -1。查找终止条件为left > right。查找第一个位置时,若该位置索引越界或者该位置数组元素不等于target,说明数组中不存在目标值。
Python3代码如下:
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = self.binarySearch(lambda x,y:x>=y,nums,target)
if left >= len(nums) or nums[left] != target:
return [-1,-1]
right = self.binarySearch(lambda x,y:x>y,nums,target)
return [left,right-1]
def binarySearch(self,compare,nums,target):
left,right = 0,len(nums)-1
while left <= right:
mid = (left + right) // 2
if compare(nums[mid],target):
right = mid - 1
else:
left = mid + 1
return left