力扣35搜索插入位置

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

请必须使用时间复杂度为 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
示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:

输入: nums = [1], target = 0
输出: 0


提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

思路：题目中说必须使用时间复杂度为O(logN)的算法，再看提示部分nums为无重复元素的升序排列数组，已经提示出要使用二分查找了。

首先构建二分查找框架

int left = 0;
int right = nums.length-1;
int num=0;
while(left 
此时观察提示，可以看出left+right不会造成溢出的情况。
 既然是有序数组，就可以根据mid和target的大小，来决定向小数的方向折半，还是向大数的方向折半。所以就有了一下三种情况：
 
（1）当nums[mid]==target时，返回mid
 
（2）当nums[mid]>target时，left=mid+1
 
（3）当nums[mid] 
即
 
if (nums[mid] == target) {
    return mid;
} else if (nums[mid] < target) {
    left = mid+1;
} else if (nums[mid] > target) {
    right = mid-1;
}
 
接下来看nums的长度，题上没有给，那默认为1到n，这时要考虑循环的终止条件left 
假设数组长度为1，那么left就等于right ， 很明显当left等于right时不满足while循环条件，所以不管target的值为多少最后都会返回-1。
 
继续考虑数组长度为2的情况，left 
很明显，少一次循环，此时就可以把while的条件改为left<=right，这样就可以完美的解决这个问题。
 

 

 
此时算法还没有结束，看题上要求，当目标值不存在数组中时，返回它将要插入的位置。
 
定义一个int类型数num=0
 
首先，既然数组中不存在该值，那么二分查找一定会运行到最后。那么我们到底要取最终的left还是最终的right。这里我们可以做一个实验。
 
再定义一个int类型数num2=0，让num2=right，num=left
 
就以第一组[1,3,5,6]为例，我们分别取0，4，7来验证最后取left还是right
 
当target=0时：left=0，right=-1
 
当target=4时：left=2，right=1
 
当target=7时：left=4，right=0
 
由此可以看出 要想返回目标值插入的位置，只需要返回left的最终值就可以了。
 
该算法时间复杂度O(logN)，空间复杂度O(1)
 
完整代码：
 
public int searchInsert(int[] nums, int target) {
	int left = 0;
	int right = nums.length-1;
	int num=0;
	while(left<=right){
	    int mid = (left+right)/2;
	    if (nums[mid] == target) {
	        return mid;
	    } else if (nums[mid] < target) {
	        left = mid+1;
	        num = left;
	    } else if (nums[mid] > target) {
	        right = mid-1;
	    }
	}
	return num;
}
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702962.html