Leetcode 34

Posted on | | 阅读数
Words count in article: 193 | Reading time ≈ 1

Question

Solution

二分查找。

找到mid=target的位置。然后查找mid附近的等于target的数的index。

首先令n=m=mid。采用while来找到对应的index。如果mid前面的数等于target，则n-=1。这里需要注意一种情况，即首位就等于target。所以额外添加了一个限制条件，即n>-1。同样，对于mid之后的元素采用相同的方法来查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 1 and nums[0] == target:
            return [0, 0]
        first, last = 0, len(nums)-1
        while first <= last:
            mid = (first + last) // 2
            if nums[mid] == target:
                n = m = mid
                while n > -1 and nums[n] == target:
                    n -= 1
                while m < len(nums) and nums[m] == target:
                    m += 1
                return [n+1, m-1]
            elif nums[mid] < target:
                first = mid + 1
            else:
                last = mid - 1
        return [-1, -1]