题解 | #找出特定体重的牛群# 二分

知识点

二分

思路

两次二分分别找到比所求段小的第一个位置和当前数字的第一个位置即可。

重要的在于二分边界条件的书写。

时间复杂度

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    int n;
    vector<int> searchRange(vector<int>& weights, int target) {
        n = weights.size();
        vector<int> res = {find(weights, target + 1), find(weights, target) - 1};
        if (res[0] > res[1]) return {-1, -1};
        return res;
    }
    int find(vector<int>& arr, int x) {
        // 找到小于x的第一个位置
        if (arr.empty() or arr.back() >= x) return n;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (arr[mid] >= x) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};