题解 | #牛群的位置排序#

知识点

二分

思路

已知数组升序，故对于target来说，可以使用二分查找插入的位置，此位置的数要么为target，要么是小于target的第一个数。

在二分前特判一下是否可能插在数组头前或者尾后即可

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param labels int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int searchInsert(vector<int>& labels, int target) {
        // write code here
        int l=0;
        int r=labels.size()-1;
        int mid;
        if(labels[r]<target)return r+1;
        if(labels[0]>target)return 0;
        while(l<r)
        {   mid=(l+r)>>1;
            if(labels[mid]<target)
            {
                l=mid+1;
            }
            else if(labels[mid]>=target)
            {
                r=mid;
            }
            else return mid;
        }
        return l;



    }
};