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

主要是二分查找法，C++的STL有对应的api:

* lower_bound()

* upper_bound()

C++实现

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        int size = nums.size();
        int left = lowerBound(nums, target);
        int right = upperBound(nums, target);
        if (left > size-1 || nums[left] != target) {
            return {-1, -1};
        }
        return {left, right-1};
    }
private:
    int lowerBound(vector& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (nums[mid] < target) { // to equal
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return low;
    }

    int upperBound(vector& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (nums[mid] <= target) { // to greater
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return low;
    }

};

golang实现

func searchRange(nums []int, target int) []int {
    // binary search with lower_bound and upper_bound
    size := len(nums)

    left := lowerBound(nums, target)
    if left > size-1 || nums[left] != target {
        return []int{-1, -1}
    }
    right := upperBound(nums, target)
    return []int{left, right-1}
}

func lowerBound(nums []int, target int) int {
    low,high := 0,len(nums)-1
    for low <= high {
        mid := (low+high)/2
        if (nums[mid] < target) { // to equal
            low = mid+1
        } else {
            high = mid-1
        }
    }
    return low
}

func upperBound(nums []int, target int) int {
    low,high := 0,len(nums)-1
    for low <= high {
        mid := (low+high)/2
        if (nums[mid] <= target) { // to greater
            low = mid+1
        } else {
            high = mid-1
        }
    }
    return low
}

参考链接

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/?envType=study-plan-v2&envId=top-interview-150