力扣 34. 在排序数组中查找元素的第一个和最后一个位置

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

题目

• 给一个非降序数组，查找 target 数字出现的第一个 index 和最后一个 index，若不存在返回 -1

思路

• 二分查找 lower bound 和 upper bound
• 对于查找 lower bound，碰到相等的数字，挪动 r 下标到 mid，逐渐向 lower 逼近
• 对于查找 upper bound，mid 需要在偶数时，取中间偏大的值，碰到相等的数字时，挪动 l 下标到 l，逐渐向 upper 逼近

代码

class Solution {
public:
    int find_lower(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) /2;
            if (nums[mid] > target) r = mid - 1;
            else if (nums[mid] == target) r = mid;
            else if (nums[mid] < target) l = mid + 1;
        }
        if (nums[l] == target) return l;
        return -1;
    }

    int find_upper(vector<int>& nums, int target) {
        if (nums.size() == 0) return -1;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2 + (l + r) % 2;
            if (nums[mid] > target) r = mid - 1;
            else if (nums[mid] == target) l = mid;
            else if (nums[mid] < target) l = mid + 1;
        }
        if (nums[r] == target) return r;
        return -1;
        
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        ans.push_back(find_lower(nums, target));
        ans.push_back(find_upper(nums, target));
        return ans;
    }
};