https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。（想到二分）
如果数组中不存在目标值，返回 [-1, -1]。
输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]本题就是二分查找的常见变体
二分查找及其变体（Python）https://blog.csdn.net/IOT_victor/article/details/91357208
class Solution(object): def searchRange(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ if len(nums) == 0: return [-1, -1] return [self.left_bound(nums, target), self.right_bound(nums, target)] # 右界：最后第一个出现index def right_bound(self, nums, target): low, high = 0, len(nums) - 1 while low <= high: mid = low + (high - low) // 2 if nums[mid] < target: low = mid + 1 elif nums[mid] > target: high = mid - 1 else: if mid == len(nums) - 1 or nums[mid + 1] != target: return mid else: # 继续在[mid+1, high]之间找 low = mid + 1 return -1 # 左界：第一个出现index def left_bound(self, nums, target): low, high = 0, len(nums) - 1 while low <= high: mid = low + (high - low) // 2 if nums[mid] < target: low = mid + 1 elif nums[mid] > target: high = mid - 1 else: # nums[mid]=target if mid == 0 or nums[mid - 1] != target: # 如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是要找的； # 如果 mid 不等于 0，但 a[mid] 的前一个元素 a[mid-1] 不等于 target，那也说明 a[mid] 就是我们要找的第一个值等于给定值的元素 return mid else: high = mid - 1 # 继续找，要找的元素出现在 [low, mid-1] 之间 return -1 nums = [5,7,7,8,8,10] target = 8 s = Solution() print(s.searchRange(nums, target))
