Find First and Last Position of Element in Sorted Array (LeetCode 34)

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
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

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

Constraints:

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums is a non decreasing array.
  • -10^9 <= target <= 10^9

这道题依然是二分查找的变体,最直接的思路就是先用二分查找找到 target 的位置,然后分别向左右扩展。这种方法不符合复杂度要求,不过却比较容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def search_range(nums: List[int], target: int) -> List[int]:
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 1
if nums[mid] == target:
start, end = mid, mid
while start >=0 and nums[start] == target:
start -= 1
while end <= len(nums) - 1 and nums[end] == target:
end += 1
return [start+1, end-1]
else:
if nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return [-1, -1]

这里有两个点需要注意:

  • 找到 target 再开始遍历时,要遍历到顶端的位置
  • 返回的时候 start 要加 1 end 要减 1,因为 while 循环最后多一次操作

显然,这个复杂度是 O(n) 的,和从头到尾遍历可以说也没啥大的区别了。要达到题目要求的复杂度就只能另辟蹊径了。

我们再想想,因为数组是有序的,那是不是可以用两次二分查找,分别找到左边的 target 和右边的 target 呢?当然可以!只要改一下每次的条件,将等于 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
26
def search_left(nums: list, target: int):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid - 1
else:
l = mid + 1
return l

def search_right(nums: list, target: int):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] <= target:
l = mid + 1
else:
r = mid - 1
return r

def search_range(nums: list, target: int):
l = search_left(nums, target)
r = search_right(nums, target)
if 0 <= l <= r < len(nums):
return [l, r]
return [-1, -1]

上面的左右两个函数可以合并为一个,最终的代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def search(nums: list, target: int, left: bool):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] > target:
r = mid - 1
elif nums[mid] < target:
l = mid + 1
else:
if left:
r = mid - 1
else:
l = mid + 1
if left:
return l
else:
return r

def searchRange(nums: list, target: int):
l = search(nums, target, True)
r = search(nums, target, False)
if 0 <= l <= r < len(nums):
return [l, r]
return [-1, -1]

看了下 Solution 的解法也是类似的,不过多做了一点优化,就是当求出 l 后,先判断是否超出 range 范围,或者所在位置的元素是否不等于 target,只要满足其一就直接返回兜底结果,这样就少计算了一次右边的情况。

总结一下可以发现其中的关键是逆向思维,也就是平时用二分查找是找那个要的 target,这里恰好是 “不要”,其实是找的 target 边上的那两个元素。算法真美妙。