题目出处
题目描述
个人解法
思路：
1.依次遍历数组，看目标值是否在数组中
2.如果不在，将目标值插入数组（涉及到数组移动、扩容），返回下标
代码示例：（Java）
todo
复杂度分析
todo
官方解法
方法1：二分查找
思路：
代码示例：（Java）
public class Solution1 {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
}
复杂度分析
- 时间复杂度：O(logn)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。
- 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
考察知识点
收获
1.二分查找思想（天下大势，分久必合，合久必分）：分治思想（大数据也用到了这种思想）
2.返回数组下标
3.数组扩容
