35.搜索插入位置

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

请必须使用时间复杂度为?O(log n)?的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例?2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums?为?无重复元素?的?升序?排列数组
• -104 <= target <= 104

这个题是经典的二分算法，但是略有改进。

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较，如果目标值小于中间元素，则在数组的左半部分继续查找，否则在右半部分查找，不断缩小搜索范围，直到找到目标值或确定目标值不存在为止。

二分查找也叫折半查找，比如在一个有序的数组里面找到目标值，它是一种查询效率比较高的算法，时间复杂度O(logn)。比如在下面数组找到 6.首先在定位到两侧，也就是最大值和最小值。并找到中间和目标值比较。

中间值是 5，比目标值更小，就要缩小范围，中间值作为最小值，在中间值右边的区域再找到中间值和目标值比较。

以此类推，一直缩小范围，直到找到目标值，或者搜索完数据。

本题就是在二分的基础上进行改进，本质和折半插入排序一致，在最后返回时，要返回low或者high+1，即要插入的位置。

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