整套网站设计,外贸网站 开源,学做网站论坛插件,seo查询爱站网题目
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5 输出: 2
示例 …题目
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5 输出: 2
示例 2:
输入: nums [1,3,5,6], target 2 输出: 1
示例 3:
输入: nums [1,3,5,6], target 7 输出: 4
提示:
1 nums.length 104
-104 nums[i] 104
nums 为 无重复元素 的 升序 排列数组
-104 target 104代码
class Solution { public int searchInsert(int[] nums, int target) { if(targetnums[0])return 0; if(targetnums[nums.length-1])return nums.length; int left0; int rightnums.length-1; while(leftright){ int midleft((right-left)1); if(targetnums[mid]){ return mid; } else if(targetnums[mid]){ rightmid-1; }else{leftmid1;}}return left;
}}
关于为什么最后返回left这里涉及到二分查找的边界条件处理。当while循环结束时意味着left right即没有找到与target相等的元素。此时left实际上就是target应该插入的位置。这是因为
在每次迭代中如果target小于中间位置的值nums[mid]我们就把右边界right移到mid - 1这意味着target应该插入到mid或者更左边。
如果target大于中间位置的值nums[mid]我们就把左边界left移到mid 1这意味着target应该插入到mid的右边。
当left超过right时left正好指向了target应该插入的位置因为在最后一次有效的比较中如果target小于nums[mid]那么right会被更新为mid - 1而left保持不变因此left是正确的位置。如果target大于nums[mid]那么left会被更新为mid 1这同样指向了target应该插入的位置因为所有比target小的数都在它的左边。所以在找不到target的情况下循环结束时的left就是target按顺序插入的位置。
暴力解法 class Solution { public int searchInsert(int[] nums, int target) { for(int i0;inums.length;i){ if(nums[i]target){ return i; } }return nums.length;
}}
