leetcode 34. 在排序数组中查找元素的第一个和最后一个位置(python)

女爷i 2022-05-14 13:06 147阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

给定一个按照升序排列的整数数组 `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(object):
        def searchRange(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            if len(nums) == 0:
                return [-1,-1]
            elif target < nums[0] or target > nums[-1]:
                return [-1,-1]
            else:
                l, r = 0, len(nums) - 1
                while l <= r:
                    mid = (l + r) // 2
                    if target > nums[mid]:
                        l = mid + 1
                    elif target < nums[mid]:
                        r = mid - 1
                    #当找到相等的值时，把左右指针合并并分别向左向右依次遍历找出上下限
                    elif target == nums[mid]:
                        l = r = mid
                        while l-1 >= 0 and nums[l-1] == target:
                            l -= 1
                        while r+1 <= len(nums)-1 and nums[r+1] == target:
                            r += 1
                        return [l,r]
            return [-1,-1]

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test