题目出处
35-搜索插入位置-题目出处
题目描述
个人解法
思路：
1.依次遍历数组，看目标值是否在数组中
2.如果不在，将目标值插入数组（涉及到数组移动、扩容），返回下标
代码示例：（Java）
todo
复杂度分析
todo
官方解法
35-搜索插入位置-官方解法
方法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.数组扩容
Gitee源码位置
35-搜索插入位置-源码
