【leetcode】34. Find First and Las

1、题目描述

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]

2、问题描述：

• 给一个排好序的数组，给一个target，查找target起始位置，和最终位置。如果没有，那么返回-1， -1.

3、问题关键：

• 有序，一般二分查找，二分的两个模版，一个是求小于等于target的最大值，一个是大于等于target的最小值。
• 一般写二分的思考顺序是这样的：首先通过题目背景和check(mid)函数的逻辑，判断答案落在左半区间还是右半区间。
  左右半区间的划分方式一共有两种：
• 1.中点mid属于左半区间，则左半区间是[l, mid]，右半区间是[mid+1, r]，更新方式是r = mid;或者 l = mid + 1;，此时用第一个模板；
• 2.中点mid属于右半区间，则左半区间是[l, mid-1]，右半区间是[mid, r]，更新方式是r = mid - 1;或者 l = mid;，此时用第二个模板；

4、C++代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return vector<int>({-1, -1});
        int n = nums.size();
        vector<int> res;
        int l = 0, r = n - 1;
        while(l < r) {
            int mid = l + r >> 1;//小于等于k的最大值。（答案在左边）
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != target) return vector<int>({-1, -1});//不存在这个数。
        res.push_back(l);
        l = 0, r = n - 1;
        while(l < r) {
            int mid = l + r + 1 >> 1;//大于等于target的最小值。（答案在右边）
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        res.push_back(l);
        return res;
    }
};