如果你从本文中学习到丝毫知识，那么请您点点关注、、评论和
大家好，我是爱做梦的鱼，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：爱做梦的鱼https://zihao.blog.csdn.net/，微信公众号、微信视频号为【程序猿干货铺】，qq交流群为：1107710098，

如果你同样热爱算法，那么请关注我，我将每日更新力扣的每日一题的题解+代码，每周更新力扣周赛题解+代码
《本题Python代码版》
专栏《力扣每日一题》
专栏《力扣周赛》
专栏《力扣大厂模拟面试算法题》

题目：35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例 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 

思路

本题需要考虑两种情况

1. 目标值存在，返回其索引。
   公式一：target = nums[pos]
2. 目标值不存在于数组中，返回它将会被按顺序插入的位置。
   1. 普遍情况，公式二：nums[pos−1] < target < nums[pos] 返回的索引为pos[1,n-1]
   2. 边界情况一，targer < nums[0] 返回的索引为0
   3. 边界情况二，target > nums[n-1] 返回的索引为n

合并公式一二，可以得出我们本题的公式三（普遍情况）。公式三：nums[pos−1] < target <= nums[pos]
「在一个有序数组中找第一个大于等于target 的下标」 （本题中提示：你可以假设数组中无重复元素。）
最终公式为，两种边界情况+公式三
targer < nums[0] 返回的索引为0
target > nums[n-1] 返回的索引为n
nums[pos−1] < target <= nums[pos] 返回的索引为pos[1,n-1]

方法一：暴力

public class SearchInsertPosition { public static void main(String[] args) { int[] a = {1, 3, 5, 6};         System.out.println(new Solution().searchInsert(a, 5));         System.out.println(new Solution().searchInsert(a, 1));         System.out.println(new Solution().searchInsert(a, 6)); } } //代码未简化 public int searchInsert(int[] nums, int target) { int n = nums.length; //先考虑边界情况，返回值最左边：0；最右边：n； //一、最左边边界情况：返回值为0  {1, 3, 5, 6}，0 if (target <= nums[0]) return 0; //二、最右边边界情况：返回值为0  {1, 3, 5, 6}，7 if (target > nums[n - 1]) return n; //三、后考虑普遍情况，返回值1 ~ n-1 {1, 3, 5, 6}，5 for (int i = 1; i < n; i++) if (target > nums[i - 1] && target <= nums[i]) return i; return -1; } 

简化代码

//简化的代码 public int searchInsert(int[] nums, int target) { //将最左边边界情况和普遍情况合并 for (int i = 0; i < nums.length; i++) if (target <= nums[i]) return i; return nums.length; //返回的是最右边边界情况 } 

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的长度。

• 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
  

方法二：二分法

代码

public class SearchInsertPosition2 { public static void main(String[] args) { int[] a = {1, 3, 5, 6};         System.out.println(new SearchInsertPosition2().searchInsert(a, 5));         System.out.println(new SearchInsertPosition2().searchInsert(a, 1));         System.out.println(new SearchInsertPosition2().searchInsert(a, 7)); } public int searchInsert(int[] nums, int target) { int n = nums.length; int left = 0; int right = n - 1; int ans = n; //ans 初值设置为数组长度可以省略边界条件的判断，因为存在一种情况是 target 大于数组中的所有数，此时需要插入到数组长度的位置。 while (left <= right) { int middle = (left + right) / 2; if (target <= nums[middle]) {                 ans = middle;                 right = middle - 1; } else {                 left = middle + 1; } } return ans; } } 

复杂度分析

• 时间复杂度：O(logn)，其中 n 为数组的长度。二分查找所需的时间复杂度为 O(logn)。

• 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
  

建议大家去看力扣官方讲解
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/search-insert-position/solution/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。