34. Find First and Last Position

题目链接

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

解题思路

先找左边界，再找右边界

代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        int left = findLeft(nums, target, 0, nums.size() - 1);
        ans.push_back(left);
        if (left == -1) {
            ans.push_back(-1);
        } else {
            ans.push_back(findRight(nums, target, left, nums.size() - 1));
        }
        return ans;
    }

    int findLeft(vector<int>& nums, int target, int l, int r) {
        if (l > r) {
            return -1;
        }
        if (target == nums[l]) {
            return l;
        }

        int m = (l + r) / 2;
        if (nums[m] > target) {
            return findLeft(nums, target, l, m - 1);
        } else if (nums[m] == target) {
            return findLeft(nums, target, l, m);
        } else {
            return findLeft(nums, target, m + 1, r);
        }
    }

    int findRight(vector<int>& nums, int target, int l, int r) {
        if (l > r) {
            return -1;
        }
        if (target == nums[r]) {
            return r;
        }

        int lr = l + r;
        int m = lr / 2;
        if (lr & 1) {
            m++;
        }

        if (nums[m] > target) {
            return findRight(nums, target, l, m - 1);
        } else if (nums[m] == target) {
            return findRight(nums, target, m, r);
        } else {
            return findRight(nums, target, m + 1, r);
        }
    }
};