【leetcode 第35题】搜索插入位置:leetcode-cn.com

我的实现思路:由于传入的数组是有序的,第一步判断数组最后一位是否小于目标值,如果小于,目标值可以插入数组尾部,直接范围数组长度。如果目标值小于数组最后一位,通过二分查找,声明 left , right , mid 三个变量,如果左边的数小于 mid,说明目标值应该插入 mid 的右边,此时 left = mid+1, 反正,right = mid。❤
这里特此说明一下,为什么 left = mid+1, right = mid?
1、因为当侯选区只有两个元素时,一旦进入中位数是左边界的逻辑,如果左边界不收缩,下次循环还会选左中位数,会造成死循环。解决方案:换成右中位数。
2、当侯选区只有两个元素时,一旦进入中位数是右边界的逻辑,如果右边界不收缩,下次选好还会选右中位数,如此下去会造成死循环。解决方案: 换成左中位数。
展开
小满小满于2019-08-17 03:50发布的图片
评论