LeetCode 0034. Find First and Last Position of Element in Sorted Array在排序數(shù)組中查找元素的第一個和最后一個位置【Medium】【Python】【二分】
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]
問題
給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target本辐。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置桥帆。
你的算法時間復(fù)雜度必須是 O(log n) 級別。
如果數(shù)組中不存在目標(biāo)值慎皱，返回 [-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]
思路
二分查找
兩次二分查找。
1. 查找 left茫多，所以 nums[mid] < target 時祈匙，才移動 left 指針
2. 查找 right，所以 nums[mid] <= target 時天揖，才移動 left 指針
3. lower_bound 返回的是開始的第一個滿足條件的位置夺欲，而 upper_bound 返回的是第一個不滿足條件的位置。所以今膊，當(dāng)兩個相等的時候代表沒有找到些阅，如果找到了的話，需要返回的是 [left, right - 1]斑唬。
時間復(fù)雜度: O(logn)
空間復(fù)雜度: O(1)
Python代碼
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# solution one: binary search
left = self.lowwer_bound(nums, target)
right = self.higher_bound(nums, target)
if left == right:
return [-1, -1]
return [left, right - 1]
def lowwer_bound(self, nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = int((left + right) / 2)
if nums[mid] < target: # <
left = mid + 1
else:
right = mid
return left
def higher_bound(self, nums, target):
# find in range [left, right)
left, right = 0, len(nums)
while left < right:
mid = int((left + right) / 2)
if nums[mid] <= target: # <=
left = mid + 1
else:
right = mid
return left
# # solution two: bisect
# left = bisect.bisect_left(nums, target)
# right = bisect.bisect_right(nums, target)
# if left == right:
# return [-1, -1]
# return [left, right - 1]
