题目:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
【二分查找】
题目中意思是:如果目标值存在数组中,找到并返回它的索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
那么目标值一定满足:nums[i-1] < target <= nums[i],如果存在目标值,返回的索引为 i ,不存在也返回应该是 i ,因此可以理解为:【在一个有序数组中找到第一个大于等于target的下标】,整体思路为:
- 设定左侧下标left = 0,右侧下标为 right = nums.length - 1;
- 计算中间下标 mid = left + (right - left) / 2(相当于mid = (left + right) /2 或 mid = (left + right) >> 1);
- 根据nums[mid] 和 target所对应的数字大小决定操作,如果相等,直接返回mid,如果target > nums[mid],则mid = left + 1,如果target < nums[mid],则mid = right - 1;
- 查找结束的条件是:left > right,查找结束还没有找到,则直接返回left。
部分操作解释:
1.mid = left + (right - left) / 2,
解:mid = left + (right - left) / 2 = left + 1/2right - 1/2left = 1/2left + 1/2right,这样做是为了防止整型溢出,举个例子,假如现在数值最多到 10,大于10就会溢出了,现在假设left = 6 right = 8;如果现在两个相加再除,6+8 = 14发生溢出了。但是是6 + (8-6)/2 则是6+1 = 7 则不会溢出。我看也有写成:long mid = left + (right - left)/2。
mid = (left + right) >> 1:是将left+right的结果右移一位,位运算右移一位相当于除以2,举个例子:1110(14),右移一位为0111(7)【右移是除,左移是乘】
2.为什么没找到target时返回left?
解:这里只讨论找不到目标值的情况,每次while循环都会使得[left, right]中的元素减少,left左边的元素都是小于target的,right右边的元素都是大于target的,最后一次while循环执行时left=right,执行完毕,left指向的就是第一个大于target的位置,right指向的就是最后一个小于target的位置,例如[3,5],target = 1,首先进入循环取mid=(0+1)/2=0,0位置上的数是3大于target,执行right-1=0,此时right=left=0,再执行最后一次循环, mid = 0, 0位置上的数是3大于target, right- 1 -0, 此时 left > right, 退出循环,退出后left=0,right=-1,故返回left。
java代码:
1 class Solution { 2 public int searchInsert(int[] nums, int target) { 3 int left = 0, right = nums.length - 1; 4 while(left <= right){ 5 int mid = left + (right - left) / 2; 6 if(target > nums[mid]){ 7 left = mid + 1; 8 }else if (target < nums[mid]){ 9 right = mid - 1; 10 }else{ 11 return mid; 12 } 13 } 14 return left; 15 } 16 }
python代码:
1 class Solution: 2 def searchInsert(self, nums: List[int], target: int) -> int: 3 left, right = 0, len(nums) - 1 4 while left <= right: 5 mid = left + ((right - left) // 2) 6 if target > nums[mid]: 7 left = mid + 1 8 elif target < nums[mid]: 9 right = mid - 1 10 else: 11 return mid 12 return left