一、🌱35. 搜索插入位置

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
来源：力扣（LeetCode）
难度：简单
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

🌴解题

这个题要求O(log n) 的算法，且就描述来看也是一个二分法的模子，也不用去考虑暴力搜索了。

二分法

不同的地方在于没有目标元素的时候要求返回一个插入的位置。那是不是在判断left<=right不成立的时候插入，而最后的时刻可能是left右移也可能是right左移导致搜索结束：
最后时刻left右移表示target大于【middle】，应该插入的就是middle右边，刚好此时left右移到该位置；
最后时刻right左移，表示target小于【middle】，应该插入的就是middle左边，而这是也正式left所指位置；
所以不管最后是哪一个操作，最后插入的位置都是left。
例如：
在这里插入图片描述
例如：

code

        int middle ;
        int left=0,right= nums.length-1;
        while(left<=right){
            middle=left+(right-left)/2;
            if(target==nums[middle])
                return  middle;
            else if(target<nums[middle]){
                right=middle-1;
            }
            else{
                left=middle+1;
            }
        }

        return left;