Leetcode34在排序数组中查找元素的第一个和最后一个位置

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]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

特殊条件下的二分搜索
执行用时：36 ms
内存消耗：14.6 MB

class Solution:
    def searchRange(self, nums: [int], target: int) -> [int]:
        if len(nums) == 0:
            return [-1, -1]
        result = []
        head = 0
        tail = len(nums)-1
        # 找开始位置
        while(1):
            mid = int((head+tail+1)/2)
            if nums[mid] == target:
                # 开始位置需要额外满足条件
                if mid == 0 or nums[mid-1] < target:
                    result.append(mid)
                    break
            # 优先考虑target在前半段
            if nums[head] <= target and target <= nums[mid-1]:
                tail = mid-1
            elif nums[mid] <= target and target <= nums[tail]:
                head = mid
            else:
                result.append(-1)
                break
        # 找结束位置
        head = 0
        tail = len(nums)-1
        while(1):
            mid = int((head+tail+1)/2)
            if nums[mid] == target:
                # 结束位置需要额外满足条件
                if mid == len(nums)-1 or target < nums[mid+1]:
                    result.append(mid)
                    break
            # 优先考虑target在后半段
            if nums[mid] <= target and target <= nums[tail]:
                head = mid
            elif nums[head] <= target and target <= nums[mid-1]:
                tail = mid-1
            else:
                result.append(-1)
                break

        return result