接外包,有相关需求的可以联系我:Telegram | Email

Find First and Last Position of Element in Sorted Array | Binary Search

该文章创建(更新)于02/27/2022,请注意文章的时效性!

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return[-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Solution

Binar search

Code

  • submit code
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        result = []

        result.append(self.left_bound(nums,target))
        result.append(self.right_bound(nums,target))

        return result

    def left_bound(self,nums,target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + int((right - left) / 2)
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                right = mid - 1

        if left >= len(nums) or nums[left] != target:
            return -1

        return  left

    def right_bound(self,nums,target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + int((right - left) / 2)
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                left = mid +1

        if right < 0 or nums[right] != target:
            return  -1

        return right

  • full code
class Solution:
    def searchRange(self, nums, target):
        result = []

        result.append(self.left_bound(nums,target))
        result.append(self.right_bound(nums,target))

        return result

    def left_bound(self,nums,target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + int((right - left) / 2)
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                right = mid - 1

        if left >= len(nums) or nums[left] != target:
            return -1

        return  left

    def right_bound(self,nums,target):
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + int((right - left) / 2)
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] == target:
                left = mid +1

        if right < 0 or nums[right] != target:
            return  -1

        return right


nums = [5, 7, 7, 8, 8, 10]
target = 8
S = Solution()
print(S.searchRange(nums,target))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/02/27/find-first-and-last-position-of-element-in-sorted-array-binary-search/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码