LeetCode-34 在排序数组中查找元素的第一个和最后一个位置 --- Python代码实现及详解

朱雀 2020-10-31 18:27 468阅读 0赞

### 题目： ###

给定一个按照升序排列的整数数组 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]

### 思路： ###

首先审题要仔细看到时间复杂度是 O(log n)就应该想到要用二分查找，但这里二分法需要变换一下：设置左右两个指针进行二分法，当通过二分法搜寻到目标值时，左右指针合一，然后在合一的位置上分别向左向右遍历寻找是否还有和目标值相等的数。

### 编码实现： ###

class Solution:
        def searchRange(self, nums: List[int], target: int) -> List[int]:
            if len(nums) == 0:
                return [-1,-1]
            elif target < nums[0] or target > nums[-1]:
                return [-1,-1]
            else:
                beg, end = 0, len(nums) - 1
                while beg <= end:
                    mid = (beg + end) // 2
                    if target > nums[mid]:
                        beg = mid + 1
                    elif target < nums[mid]:
                        end = mid - 1
                    # 当找到相等的值时，把左右指针合并并分别向左向右依次遍历找出上下限
                    elif target == nums[mid]:
                        beg = end = mid
                        while beg-1 >= 0 and nums[beg-1] == target:
                            beg -= 1
                        while end+1 <= len(nums)-1 and nums[end+1] == target:
                            end += 1
                        return [beg,end]
            return [-1,-1]