知识点
二分
思路
已知数组升序,故对于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;
}
};