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

考察知识点

• 二分查找
• STL使用（lower_bound()函数）

题目解析

题意

在一个递增排序的数组labels中以时间复杂度为O(log n)的算法查找给定的目标值target的位置，如果不存在，返回它按顺序插入的位置。

解析

根据递增排序的数组、时间复杂度O(log n)可知二分查找算法完全符合这一性质。 此题采用C++ STL标准库给出了lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。

AC code(C++)

class Solution {
public:
    int searchInsert(vector<int>& labels, int target) {
        int index = 0;
        index = lower_bound(labels.begin(),labels.end(),target)-labels.begin();
        return index;
    }
};