LeetCode 34 Search for a Range

Posted on | In | 阅读

用不同的二分查找方式找到最左边和最右边的target

Given an array of integers nums sorted in ascending order, 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].

Example 1:

1
2
3
> Input: nums = [5,7,7,8,8,10], target = 8
> Output: [3,4]
>

Example 2:

1
2
3
> Input: nums = [5,7,7,8,8,10], target = 6
> Output: [-1,-1]
>

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return [-1, -1]
        l = 0
        r = len(nums)-1
        # left most
        while l <= r:
            mid = (l+r) // 2
            if nums[mid] >= target:
                r = mid-1
            else:
                l = mid+1
        if l >= len(nums) or nums[l] != target:
            return [-1, -1]
        left = l

        l = 0
        r = len(nums)-1
        # right most
        while l <= r:
            mid = (l+r) // 2
            if nums[mid] > target:
                r = mid-1
            else:
                l = mid+1
        right = r
        return [left, right]