给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
解题思路参考精选题解:
解法：二分查找
如果该题目暴力解决的话需要 O(n)O(n) 的时间复杂度，但是如果二分的话则可以降低到 O(logn)O(logn) 的时间复杂度
整体思路和普通的二分查找几乎没有区别，先设定左侧下标 left 和右侧下标 right，再计算中间下标 mid
每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则 left 右移，nums[mid] > target 则 right 左移
查找结束如果没有相等值则返回 left，该值为插入位置
时间复杂度：O(logn)O(logn)
二分查找的思路不难理解，但是边界条件容易出错，比如 循环结束条件中 left 和 right 的关系，更新 left 和 right 位置时要不要加 1 减 1。作者：guanpengchn
链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-35-sou-suo-cha-ru-wei-zhi-by-guanp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public static int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 上面这行代码可以换成 int mid = (left + right ) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return left;
}
至于为什么一定得返回左边界 left，我就直接copy了另一个作者的解析
如果返回右边界 right 提交代码不会通过
【注意】下面我尝试说明一下理由，如果你不太理解下面我说的，那是我表达的问题
但我建议你不要纠结这个问题，因为我将要介绍的二分查找法模板，可以避免对返回 left 和 right 的讨论
理由是对于 [1,3,5,6]，target = 2，返回大于等于 target 的第 1 个数的索引，此时应该返回 1
在上面的 while (left <= right) 退出循环以后，right < left，right = 0 ，left = 1
根据题意应该返回 left，
如果题目要求你返回小于等于 target 的所有数里最大的那个索引值，应该返回 right
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/two-sum/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 个人的暴力遍历法:
解题思路:
第一步:假设数组中存在target,那么遍历一遍,找到该target所属的下标
除了第一步是存在target外,以下的步骤都是不存在target的判断逻辑
第二步:如果该数组长度为1,直接判断大于还是小于0角标的元素,直接返回
第三步:因为要判断一个元素和后一个元素与target之间的关系,所以在循环条件中,就要将数组长度 - 1 ,避免溢出数组,然后判断
第1种情况:target比数组中所有元素都要小
第2种情况:target比数组中的一个元素大,比后一个元素小,那就返回后一个元素的下标
第3种情况:target比数组中所有元素都要大,前提是循环已经来到了数组的末尾,这里用 i + 2 == nums.length 来做是否到达数组末尾的判断.
时间复杂度为 o(n²)
public static int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target)
return i;
}
if (nums.length == 1) {
if (nums[0] > target)
return 0;
return 1;
}
for (int i = 0; i < nums.length - 1; i++) {
if (nums[0] > target)
return 0;
else if (nums[i] < target && target < nums[i + 1])
return i + 1;
else if (i + 2 == nums.length && nums[i + 1] < target) {
return i + 2;
}
}
return -1;
}
网友评论