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

本文主要是介绍leetcode34.在排序数组中查找元素的第一个和最后一个位置 Python，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路：

二分查找，根据要求的时间复杂度，肯定要用二分查找，这里要进行两次二分查找，第一次是要找大于或者等于目标值的左边界，第二次是要找第一个大于目标值的元素索引，这个索引位置减1就是结束位置。

写一个二分查找的函数，然后两次调用此函数找到开始和结束位置，找结束位置将目标值加1,来找第一个大于目标值的元素索引，最后得到开始和结束位置。

先判断如果开始位置索引等于数组长度，说明一直找到最后一个元素都没找到大于或者等于目标值的元素，或者返回的开始位置的数，确实大于目标值，但是不等于目标值，都说明数组中没有这个元素，直接返回[-1,-1]，否则，返回两个索引位置构成的数组。

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1,-1]
        def binarysearch(numss,target):
            left,right = 0,len(nums)-1
            while left <= right:# 当左右指针相等时，也需要判断是否符合条件
                mid = (left + right) // 2
                if nums[mid] >= target:# 找大于等于目标值的左边界
                    right = mid - 1
                else:
                    left = mid + 1
            return left
        start = binarysearch(nums,target)
        end = binarysearch(nums,target+1) - 1 # 找第一个大于目标值的元素索引，再减1就是结束位置
        # if nums[start] != target or start == len(nums): 条件1满足了，后边索引就会报错
        if start == len(nums) or nums[start] != target:
            # 如果最后一个元素都不是目标值，或者找到的索引位置的数不是目标值
            return [-1,-1]
        else:
            return [start,end]

这篇关于leetcode34.在排序数组中查找元素的第一个和最后一个位置 Python的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！