知识点

二分、STL

文字分析

题意：给定一个升序数组labels，返回第一个大于等于target的下标。要求时间复杂度为O(logn)。

由于数组是升序的，满足二分的前置要求。改题可以用二分来解，也可以直接调用C++中STL封装的lower_bound()来解。

编程语言

c++

编程代码

1.lower_bound函数

class Solution {
public:
    int searchInsert(vector<int>& labels, int target) {
        // write code here
         return lower_bound(labels.begin(),labels.end(),target) - labels.begin();
    }
    
};

2.自己写二分

class Solution {
public:
    int searchInsert(vector<int>& labels, int target) {
        // write code here
        int l = 0,r = labels.size() - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(labels[mid] < target) l = mid + 1;
            else  r = mid - 1;
        }
        return l;
    }
    
};