给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2
示例 2:
输入: [1,3,5,6], 2 输出: 1
示例 3:
输入: [1,3,5,6], 7 输出: 4
示例 4:
输入: [1,3,5,6], 0 输出: 0
Related Topics
题解
把头尾情况单独处理了去掉,剩下的用二分法无限逼近目标位置,得到left的值
之后再再小区间内做个遍历循环,二分法本身应该是有办法可以取到准确的目标位置的,但是这个里面边界判断的情况实在是有点头疼,于是就取个巧,最终位置无限逼近之后,再前后扩展一位进行大小判断
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public static int searchInsert(int[] nums, int target) {
//请在此作答
if(null==nums || nums.length == 0 || target < nums[0] || nums[0] == target){
return 0;
}
if (nums[nums.length-1] == target){
return nums.length-1;
}
if (nums[nums.length-1] < target){
return nums.length;
}
int left = 0;
int right = nums.length-1;
while (left < right){
int mid = left + (right-left)/2;
if (nums[mid] == target){
return mid;
}
if (nums[mid] > target){
right = mid-1;
}else{
left = mid+1;
}
}
for (int i = left-1; i <= left+1; i++) {
if (i<0 || i>= nums.length){
continue;
}
if (nums[i] == target){
return i;
}
if (nums[i] < target && nums[i+1] > target){
return i+1;
}
}
return left;
}
}
//leetcode submit region end(Prohibit modification and deletion)
发表评论