每天一题LeetCode【第26天】

T35. Search Insert Position【Easy】

题目

给定排好序的整数数组和一个目标数(target)，若目标数在数组中存在，则返回目标数的 index 值。如果不存在，则返回目标数按顺序插入数组时应该插入位置的 index 值。

你可以假设数组中没有重复的数字。

这里举了几个例子，
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

思路

主要就还是二分法，另外就是要注意，返回的是low!

具体还是看代码和注释好了~

代码

代码取自 Top Solution，稍作注释

public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length-1;
        while(low<=high){
            //二分法找中间值
            int mid = (low+high)/2;
            //如果匹配，则返回index
            if(nums[mid] == target) return mid;
            //二分法常用：若中间大于 target,则target在low~mid-1之间,把high赋值为mid-1
            else if(nums[mid] > target) high = mid-1;
            //二分法常用：若中间小于 target,则target在mid-1~high之间,把low赋值为mid-1
            else low = mid+1;
        }
        //返回low，这里不能返回high，因为low最后的值一定恰好小于target的数+1，而high最后的值一定恰好大于target的数-1
        return low;
    }

补充

这两天做的都有用到二分法~这是比较简单的一道，想看看其他二分法的用法，可以看看我前两天的博客 <(￣︶￣)>

这一题呢，就是让我开始思考二分法执行以后 low 和 high 的值最后的归宿。