LC35.SearchinsertPosition

搜索插入位置
给定一个排序数组，寻找数组中目标值的位置，如果不存在，返回目标值应该插入的位置
要求算法时间复杂度为O(log n)

二分查找变种
O(log n)使用二分查找
该题转化为寻找目标数组中大于等于目标值的元素的位置（左边界二分查找）

#include <iostream>
#include <vector>
#include <algorithm>

class Solution
{
public:
	int searchInsert(std::vector<int>& nums, int target)
	{
		int left = 0, right = 0, mid = 0;
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (nums[mid] < target) left = mid + 1;
			else right = mid - 1;
		}
		return left;//left最终会落在一个大于等于target值上
	}

};

//also
class Solution_
{
public:
	int searchInsert(std::vector<int>& nums, int target)
	{
		return std::lower_bound(nums.begin(), nums.end(), target) - nums.begin();
	}

};