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

题目考察的知识点：二分查找

题目解答方法的文字分析：用递归进行查找，保留最小和最大的坐标。

本题解析所用的编程语言：c++

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    void search(vector<int>& weights, int& target, vector<int>& v, int left, int right)
    {
	    //判断临界
        if (right - left <= 1)
        {
            if (weights[left] == target)
            {
                v[0] = v[0] == -1 ? left : min(v[0], left);
                v[1] = max(v[1], left);
            }
            if (weights[right] == target)
            {
                v[0] = v[0] == -1 ? right : min(v[0], right);
                v[1] = max(v[1], right);
            }
            return;
        }
        int mid = (left + right) / 2 ;
        if (weights[mid] > target)
            search(weights, target, v, mid, right);
        else if (weights[mid] < target)
            search(weights, target, v, left, mid);
        else  
        {
            v[0] = v[0] == -1 ? mid : min(v[0], mid);
            v[1] = max(v[1], mid);
            search(weights, target, v, left, mid);
            search(weights, target, v, mid, right);
        }
    }
    vector<int> searchRange(vector<int>& weights, int target) {
        // write code here
        vector<int> v(2, -1);
        if (weights.size() == 0)
            return v;
        search(weights, target, v, 0, weights.size() - 1);
        return v;
    }
};