[Lintcode]61. Search for a Range/[Leetcode]34. Find First and Last Position of Element in Sorted Array
本题难度: Medium/Medium
- Topic: Binary Search
- Description
- Given a sorted array of n integers, find the starting and ending position of a given target value.
- If the target is not found in the array, return [-1, -1].
- Example
- Example 1:
- Input:
- []
- 9
- Output:
- [-1,-1]
- Example 2:
- Input:
- [5, 7, 7, 8, 8, 10]
- 8
- Output:
- [3, 4]
- Challenge
- O(log n) time.
我的代码
- class Solution:
- def searchRange(self, nums, target):
- """
- :type nums: List[int]
- :type target: int
- :rtype: List[int]
- """
- l = 0
- r = len(nums) - 1
- m = int((l + r) / 2)
- r1 = -1
- r2 = -1
- while (l <= r):
- if nums[m] == target and (m == 0 or nums[m - 1] <target):
- r1 = m
- r2 = m
- l += 1
- break
- else:
- if nums[m]>= target:
- r = m - 1
- else:
- l = m + 1
- m = int((l + r) / 2)
- r = len(nums) - 1
- while (l <= r):
- if nums[m] == target and (m == r or nums[m + 1]> target):
- r2 = m
- break
- else:
- if nums[m] <= target:
- l = m + 1
- else:
- r = m - 1
- m = int((l + r) / 2)
- return [r1,r2]
别人代码
- def searchRange(self, nums, target):
- def search(n):
- lo, hi = 0, len(nums)
- while lo <hi:
- mid = (lo + hi) / 2
- if nums[mid]>= n:
- hi = mid
- else:
- lo = mid + 1
- return lo
- lo = search(target)
- return [lo, search(target+1)-1] if target in nums[lo:lo+1] else [-1, -1]# 处理得很舒服
- def searchRange(self, nums, target):
- lo = bisect.bisect_left(nums, target)
- return [lo, bisect.bisect(nums, target)-1] if target in nums[lo:lo+1] else [-1, -1]
思路
同类问题 [Lintcode] 14. First Position of Target https://www.cnblogs.com/siriusli/p/10353399.html 但要注意, 最后一个元素和第一个元素一个二分查找法是无法实现的.
时间复杂度: O(log(n))
[Lintcode]61. Search for a Range/[Leetcode]34. Find First and Last Position of Element in Sorted Array
来源: http://www.bubuko.com/infodetail-2949035.html