1. 题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1: 输入: [1,3,5,6], 5 输出: 2

示例 2: 输入: [1,3,5,6], 2 输出: 1

示例 3: 输入: [1,3,5,6], 7 输出: 4

示例 4: 输入: [1,3,5,6], 0 输出: 0

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/search-insert-position 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

第一眼，遍历。再看一眼，二分。

3. 代码

3.1. 遍历

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i=0;i<nums.size();++i){
            if(nums[i]>=target) return i; 
        }
        return nums.size();
    }
};

3.2. 二分

以下三种解法中，此题中速度最快的为左闭右闭。

3.2.1. 左开右开

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=-1,right=nums.size(),mid;
        while(left+1!=right){
            mid=(left+right)>>1;
            if(nums[mid]>target) right=mid;
            else if(nums[mid]<target) left=mid;
            else return mid;
        }
        return right;
    }
};

3.2.2. 左闭右开

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

3.2.3. 左闭右闭

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