LeetCode #34：Find First And Last Position Of Element In Sorted Array(在排序数组中查找元素的第一个和最后一个位置)

题目描述

本题是一个和二分查找相关的综合性问题，大致思路就是分别找到目标值在数组中的左边界和右边界，再返回区间即可。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();

        if(n == 0) {
            return {-1, -1};
        }

        vector<int> res(2, 0);

        int l = 0;
        int r = n - 1;

        // 寻找左边界
        while(l < r) {
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // 若左边界找不到则说明数组中不存在目标值
        if(nums[l] != target) {
            return {-1, -1};
        }

        res[0] = l;

        l = 0;
        r = n - 1;

        // 寻找右边界
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        res[1] = l;

        return res;
    }
};