35. Search Insert Position
题目描述：
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
题目翻译
给定一个target，和有序序列，如果target在序列中，则返回其索引，否则给出当插入target且不改变序列性质时插入的位置（索引）。
解题方案
标签： 二分查找
思路： 思路是二分查找，找到就很简单直接返回，没找到，这个时候判断nums[low]和target的关系。
注意一点，比如说现在序列为 0 1 2 3 4 5 6 现在加入target是2，且low为1（nums[low]\==1），则返回索引为low+1 =2 如果target是0，且low为1（nums[low]\==1），则返回索引就是low而不是low-1了。具体原因画一下就清楚了。
这个题的关键还是考察二分查找完成时索引low和索引high的状态。
代码：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size() - 1;
int low = 0;
int high = len - 1;
int mid;
while (low <= high)//标准二分查找
{
mid = low + (high - low) / 2;
if (nums[mid] == target)
return mid;//找到元素
else if (nums[mid] > target)
high = mid - 1;
else
low = mid + 1;
}
//没找到时判断与nums[low]的关系
if (target > nums[low])
return low + 1;
else
return low;
}
};