[Leetcode]34. Find First and Last Position of Element in Sorted Array(C++)

题目描述

题目链接：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.

If target is not found in the array, return [-1, -1].

例子

例子 1

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

例子 2

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

例子 3

Input: nums = [], target = 0 Output: [-1, -1]

Follow Up

Could you write an algorithm with O(log n) runtime complexity?

Constraints

0 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

nums is a non-decreasing array.

-10^9 <= target <= 10^9

解题思路

给定一个排序好的数组和一个目标值，要求在指数时间内找到数组中出现的第一个和最后一个该目标值的位置。由于要求指数时间所以思路是从二分查找出发。在搜索到目标值时，由于要找到第一个和最后一个目标值的位置，可以想到同样用二分查找分别查找，不过问题变成了：

找第一个位置：给定数组 [a, b, b, b]，找到第一个 b 的位置，二分查找如下
- Mid >= b （事实上只可能等于），表面右侧有收缩空间，收缩右边界 right = mid (mid 本身还在搜索范围中)
- 否则，收缩左边界，因为 Mid != b，所以 left = mid + 1
找最后一个目标值位置：给定数组 [b, b, b, a]，找到最后一个 b 的位置，二分查找如下：
- 由于 (left + right) / 2 是往下取整，所以有可能会出现 mid == left，如果用　mid 作为基准值的话，我们收缩 left 的时候要考虑 mid 还在搜索范围中不能让 left = mid + 1，因此这里选 mid + 1 作为中间值
- Mid + 1 <= b （只可能等于）：表明左侧有收缩空间，令 left = mid + 1
- 否则收缩右边界　right = mid

代码如下：

#include <vector>
class Solution {
public:
    std::vector<int> searchRange(std::vector<int>& nums, int target) {
        if (nums.empty()) {
            return {-1, -1};
        }

        int first = -1;
        int last = -1;
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                // find first element
                int first_right = mid;
                int first_left = left;
                while (first_left < first_right) {
                    int first_mid = (first_left + first_right) / 2;
                    if (nums[first_mid] >= target) {
                        first_right = first_mid;
                    } else {
                        first_left = first_mid + 1;
                    }
                }

                // find last element
                int last_right = right;
                int last_left = mid;
                while (last_left < last_right) {
                    int last_mid = (last_left + last_right) / 2;
                    if (nums[last_mid + 1] <= target) {
                        last_left = last_mid + 1;
                    } else {
                        last_right = last_mid;
                    }
                }

                first = first_left;
                last = last_right;
                break;

            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // if last iteration end because of left == right, need to confirm the
        // only element is target
        if (left == right && nums[left] == target) {
            first = left;
            last = left;
        }

        return {first, last};
    }
};

时间复杂度:　O(log n)
空间复杂度: O(1)

GitHub 代码同步地址： 34.FindFirstAndLastPositionOfElementInSortedArray.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions