[LeetCode]题解（python）：034-Search for a Range

题目来源

https://leetcode.com/problems/search-for-a-range/

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

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

题意分析

Input: a list and a target(int)

Output: a list with the first index and the last index of target in the input list

Conditions:时间复杂度为0（logn），两个index分别为起始和最后位置

题目思路

本题可采用二分查找的算法，复杂度是0（logn）,首先通过二分查找找到taregt出现的某一个位置，然后以这个位置，以及此时的（first，last）来二分查找最左出现的位置和最右出现的位置

PS：注意边界条件

AC代码（Python）

 _author_ = "YE"

 # -*- coding:utf-8 -*-

 class Solution(object):

     def findRight(self, nums, first, mid):

         if nums[first] == nums[mid]:

             return mid

         nmid = (first + mid) // 2

         if nmid == first:

             return first

         if nums[nmid] == nums[first]:

             return self.findRight(nums, nmid, mid)

         else:

             return self.findRight(nums,first, nmid)

     def findLeft(self, nums, mid, last):

         if nums[mid] == nums[last]:

             return mid

         nmid = (mid + last) // 2

         if nmid == mid:

             return last

         if nums[nmid] == nums[last]:

             return self.findLeft(nums, mid, nmid)

         else:

             return self.findLeft(nums,nmid + 1, last)

     def searchRange(self, nums, target):

         """

         :type nums: List[int]

         :type target: int

         :rtype: List[int]

         """

         last = len(nums)

         first = 0

         while first < last:

             mid = (first + last) // 2

             # print(first,mid,last)

             if nums[mid] == target:

                 # print(self.findLeft(nums,first, mid))

                 # print(self.findRight(nums,mid,last - 1))

                 return [self.findLeft(nums,first, mid), self.findRight(nums,mid,last - 1)]

             elif nums[mid] < target:

                 first = mid + 1

             else:

                 last = mid

         return [-1,-1]

巴特西

[LeetCode]题解（python）：034-Search for a Range

最新文章

热门文章