Leetcode 34. Find First and Last Position of Element in Sorted Array

发表于 | 分类于

问题描述

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:

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

Example 2:

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

解题思路

对数时间复杂度，优先考虑二分查找，先找出目标数的左界。通常做法，二分查找对于右指针的更新改为mid而不是mid-1。然后查找target的右界，同样使用二分查找。

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
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1,-1]
        n = len(nums)
        l = 0
        r = n-1
        while l < r:
            m = (l + r) // 2
            if nums[m] < target:
                l = m + 1
            else:
                # 对于有界的更新进行改动，这样可以保证找到的m一定是target左界
                r = m
        if nums[l] != target: return -1, -1
        left = l
        l, r = left, n-1
        while l < r:
            m = (l+r) // 2 + 1
            # 对条件进行改动，使其找到的是第一个非target，即为右界
            if nums[m] == target:
                l = m
            else:
                r = m-1
        return left, l