通辽市做网站公司,舜元建设集团官方网站,深圳网站建设制作优化,网站改版合同书搜索插入位置
一共会出现下面四种情况#xff1a; 目标值在数组所有元素之前 目标值等于数组中某一个元素 目标值插入数组中的位置 目标值在数组所有元素之后
首先在二分查找的代码之前处理掉目标值在数组所有元素之前和之后的情况如果目标值在数组中的某个位置#xff0c…搜索插入位置
一共会出现下面四种情况 目标值在数组所有元素之前 目标值等于数组中某一个元素 目标值插入数组中的位置 目标值在数组所有元素之后
首先在二分查找的代码之前处理掉目标值在数组所有元素之前和之后的情况如果目标值在数组中的某个位置正常的二分查找的代码即可处理所以主要看如何处理[目标值插入数组中的位置]的情况
如果使用while(leftright)的二分查找的写法可以发现数组中没有目标值的时候最后结束循环的时候leftright更准确地说是leftright1 而且每次结束循环的时候midright、nums[right]是最接近目标值且小于目标值的一个值。 所以如果要插入到数组中插入的位置就是left的这个位置。
class Solution {public int searchInsert(int[] nums, int target) {if(targetnums[nums.length-1])return nums.length;if(targetnums[0])return 0;int left0,rightnums.length-1;while(leftright){int midleft(right-left)/2;if(nums[mid]target){rightmid-1;}else if(nums[mid]target){leftmid1;}else{return mid;}}return left;}
}
