35. Search Insert Position

本题可以使用二分查找求解。代码如下：

class Solution { public: int searchInsert(vector<int>& nums, int target) { int beg = 0, end = nums.size() - 1; while (beg <= end) { int mid = beg + (end - beg) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] > target) { end = mid - 1; } else { beg = mid + 1; } } return beg; } };

或者可以直接使用STL的函数lower_bound:

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

STL相关函数说明： 相关函数说明：

_FwdIt lower_bound(_FwdIt first, _FwdIt last,const _Tp& val)

返回一个非递减序列（[first, last)）中第一个大于等于val值的迭代器。STL同样使用二分查找法实现其源码。

_FwdIt upper_bound(_FwdIt first, _FwdIt last,const _Tp& val)

返回一个非递减序列（[first, last)）中第一个小于等于val值的迭代器。STL同样使用二分查找法实现其源码。