473b66fdd69fef4824caf6c81c8566b9
(难度Medium) Problem 34. Find First and Last Position of Element in Sorted Array(寻找元素上下界)

链接

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

难度等级

Medium

题干

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].

题意

给定一个有序的数组,以及一个int类型的target,查找这个target在数组当中的区间。如果target不存在数组当中,则返回[-1, -1]

另外要求整个算法的复杂度是$O(logN)$

样例

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]

题解

题目要求了我们要在$O(logN)$的时间内求到结果,显然,这又是一道二分的问题。

熟悉C++的同学应该不会陌生,在C++的STL当中有两个非常常用的系统函数:lower_bound和upper_bound,分别用来二分查找某一个元素的上届和下届,显然,只要我们找到了这样的上下界,整个问题就解决了。

OK,我们先从下届入手,我们怎么在一个数组当中找到某一个元素的最右侧的元素呢?

其实比较简单,那就是我们在二分的时候每次拿到的mid元素,只要当它小于活等于target,那么,l = mid。这样就能保证即使mid找到了target,也还是会往右移动。这样,只要当l的移动停止的时候,我们就找到了答案。

写成伪代码如下:

while r - l > 1:
    m = (l + r) / 2
    if nums[m] <= target:
        l = m
    else r = m
top Created with Sketch.