LeetCode100之搜索插入位置(35)--Java

1.问题描述

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

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

难度等级

简单

题目链接

搜索插入位置

2.解题思路

这道题要求我们在一个排好序的数组中找到目标值，如果目标值不存在，就找出目标值插入的位置索引，对二分查找熟悉的，应该很快就能想到这是一道非常典型的二分查找题目。

首先，确定左右指针分别为数组的起始索引和末尾索引，然后我们还需要一个中间索引来进行比较二分。在正式进行二分查找之前，我们可以像比较目标值是否小于数组的最小值，如果目标值小于数组的最小值的话，那压根就不用查找了，直接将目标值插入到数组的前面就好了；同样的道理，如果目标值大于数组的最大值，那直接插入在数组的末尾就好了。

java">        //左int left = 0;//右int right = nums.length - 1;//判断是否目标值小于给定数组的最小值if(nums[left] > target){return 0;}//判断是否目标值大于给定数组的最大值if(nums[right] < target){return nums.length;}int mid = 0;

然后，我们就可以用一个while循环开始开始进行二分查找了，只要左指针小于等于右指针，那么就是还没有查找用，可以不断循环查找逻辑。

java">        //开始二分查找while(left <= right){......}

首先，我们要更新一下中间索引，这里无论是(右指针-左指针) / 2+左指针，还是(左指针+右指针) / 2都可以，两者唯一的不同就是当左右指针都非常大的时候，前者不容易出现数值溢出的情况，而后者容易出现数值溢出的情况。

接着，比较中间值是否为我们要的目标值，是的话就可以退出二分循环了；

java">            //中间mid = (right - left) / 2 + left;//判断中间值是否等于目标值if(nums[mid] == target){return mid;}

如果中间值小于我们的目标值，说明我们要找的目标值在中间值右边，所以就要将左指针移动到中间值的下一位，进行下一轮的二分查找，但是在正式进入下一轮之前，我们要进行一个判断，如果此时移动完的左指针所指向的值大于目标值，那么目标值不存在于我们的数组当中，此时要返回目标值插入的位置，也就是中间值的下一位，当前左指针所在的位置。

举个例子 1 2 4 7 8 ,target= 6,此时如果mid = 2 ,nums[mid] = 4 ，4 < 6，left = mid+1 = 3，nums[left] = 7 ,7 > 6，那么4 < target < 7，所以target 要插在nums[mid] = 4之后，也就是mid+1的位置。

java">            //判断中间值是否小于目标值if(nums[mid] < target){left = mid + 1;//如果更新后的左索引的值大于目标值，说明目标值在数组中不存在if(nums[left] > target){mid = left;break;}}

如果中间值大于我们的目标值，说明我们要找的目标值在中间值的左边，所以就要将右指针移动到中间值的前一位，进行下一轮的二分查找，但是在正式进入下一轮之前，我们要进行一个判断，如果此时移动完的右指针所指向的值小于目标值，那么目标值不存在于我们的数组中，此时要返回目标值插入的位置，也就是中间值所在的位置。

举个例子 1 2 4 7 8 ,target= 3,此时如果mid = 2 ,nums[mid] = 4 ，4 > 3，right = mid - 1 = 1，nums[right] = 2 ,2 < 3，那么2 < target < 4，所以target 要插在nums[mid-1] = 2之后，也就是mid的位置。

java">            //判断中间值是否小于目标值if(nums[mid] < target){......}}else{right = mid - 1;//如果更新后的右索引的值小于目标值，说明目标值在数组中不存在if(nums[right] < target){break;}}

到这里，二分查找的逻辑就结束了，最后将查找到的索引进行返回就可以了。

3.代码展示

java">class Solution {//二分查找public int searchInsert(int[] nums, int target) {//左int left = 0;//右int right = nums.length - 1;//判断是否目标值小于给定数组的最小值if(nums[left] > target){return 0;}//判断是否目标值大于给定数组的最大值if(nums[right] < target){return nums.length;}int mid = 0;//开始二分查找while(left <= right){//中间mid = (right - left) / 2 + left;//判断中间值是否等于目标值if(nums[mid] == target){return mid;}//判断中间值是否小于目标值if(nums[mid] < target){left = mid + 1;//如果更新后的左索引的值大于目标值，说明目标值在数组中不存在if(nums[left] > target){mid = left;break;}}else{right = mid - 1;//如果更新后的右索引的值小于目标值，说明目标值在数组中不存在if(nums[right] < target){break;}}}//返回目标值索引或待插入位置索引return mid;}
}