“给定一个排序好的整数数组和一个目标值,在数组中找到目标值,返回其索引。如果目标值不存在数组中,就将目标值插入数组中按顺序的正确位置中。”
题目链接:
来源:力扣(LeetCode)
链接:35. 搜索插入位置 - 力扣(LeetCode) (leetcode-cn.com)
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
这个题的意思是找到排序数组中是否存在一个目标值,那么首先会想到的就是使用二分法在O(log n)的时间内找到是否存在目标值。
但这题还有额外的条件,就是数组中不存在目标值的话,返回按顺序插入的位置。
接着就是找到大于等于target的下标。
代码参考:
public class Solution {
public int SearchInsert(int[] nums, int target) {
int low = 0;
int high = nums.Length - 1;
int mid = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (target == nums[mid]) return mid;
else if (target > nums[mid]) low = mid + 1;
else high = mid - 1;
}
if (target > nums[mid]) return mid + 1;
else return mid;
}
}
时间复杂度 : O(log n)
其中n为nums数组的大小,时间复杂度为二分查找的时间复杂度O(log n)
空间复杂度: O(1)
只需要常数级别的空间存放变量。
二分查找的思路不难理解,但是边界条件容易出错。
比如 循环结束条件中 left 和 right 的关系,更新 left 和 right 位置时要不要加 1 减 1。
设置数组长度可以忽略边界条件的判断,因为存在一种情况是target大于数组中的所有数,此时需要插入到数组长度的位置。