大庆 网站制作推广普通话标语

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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(target<nums[0])return 0;
if(target>nums[nums.length-1])return nums.length;
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=left+((right-left)>>1);
if(target==nums[mid]){
return mid;
}
else if(target<nums[mid]){
right=mid-1;

        }else{left=mid+1;}}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 i=0;i<nums.length;i++){
if(nums[i]>=target){
return i;
}

    }return nums.length;
}

}