LeetCode真题 搜索插入位置

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

例子：输入: [1,3,5,6], 5  输出: 2  输入: [1,3,5,6], 2  输出: 1  输入: [1,3,5,6], 7输出: 4  输入: [1,3,5,6], 0 输出: 0

解题思路：

        当看到升序，查值就自然而然想到二分法，先用二分法找到目标值，这个很简单，套用模板就对了，但是当这个目标值不存在，就要考虑这个目标值能放在哪，此时如果用插入法进行遍历（寻找比目标值大的元素，一旦发现即返回数组元素的索引）查找，无疑增加了时间复杂度，于是我想到了二分法的left与right指针所在位置，

经过测试分两种情况讨论，

一、如果left与right指针都离开过起始位置，那么只需计算while循环结束后，left指针指向的元素必然移动到了right的后方，那么需要考虑的就是arr[left]是否大于目标值，若是则返回left索引号，否之返回left+1。

二、left与right指针有一个不曾离开过起始位置(考虑数组满溢的情况)，那么简单直接考虑是否大于数组最后一个元素，或者小于数组第一个元素。

var searchInsert = function(nums, target) {

        let l=0;

        let r=nums.length-1;

        let mid = (l+r)>>>1;

        if(target>nums[r]) return r+1;

        if(target<nums[l]) return 0;

        while(l<=r){

            if(target==nums[mid]) return mid;

            if(target<nums[mid]){

                    r = mid -1;

             }else{

                    l = mid +1;

                 }

          }

            if(nums[l]>target){

                return l

            }else {

                return l+1  

        }

 };