博客

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.



[1,3,5,6]

, 5 → 2



[1,3,5,6]

, 2 → 1



[1,3,5,6]

, 7 → 4


[1,3,5,6]

, 0 → 0

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

已排序的数组中如果有要插入的数组子，直接返回下标，即mid。

若没有，则会一直查到到low》high  此时 返回low即可