34. Find First and Last Position of Element in Sorted Array

O(logn) time

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def find(b, e, t):
            while b < e:
                m = b + (e - b) // 2
                if nums[m] < t:
                    b = m + 1
                else:
                    e = m
            return b
        n = len(nums)
        l = find(0, n, target)
        if l == n or nums[l] != target:
            return [-1, -1]
        return [l, find(l + 1, n, target + 1) - 1]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int i = lb(nums, 0, n, target);
        if (i == n || nums[i] != target) return {-1, -1};
        return {i, lb(nums, i, n, target + 1) - 1}; // 找大一号的数即可，且可以从下界找起
    }

    int lb(const vector<int> &nums, int l, int r, int target) {
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto lb = lower_bound(begin(nums), end(nums), target);
        if (lb == end(nums) || *lb != target) return {-1, -1};
        auto ub = upper_bound(begin(nums), end(nums), target);
        return {lb - begin(nums), ub - 1 - begin(nums)};
    }
};