题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，如果找不到则返回可以将其插入的位置以保证数组仍然有序。
你可以假设数组中无重复元素。
示例 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
思路及实现
方式一：二分查找
思路
题目要求在一个有序数组中查找目标值，如果找不到则返回可以将其插入的位置以保证数组仍然有序。由于数组是有序的，所以我们可以使用二分查找算法来优化搜索过程。
二分查找的基本思路是，每次取数组的中间元素与目标值进行比较：
- 如果中间元素正好是要查找的目标值，则搜索结束；
- 如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
在二分查找的过程中，我们可以同时记录可以插入目标值的位置。如果目标值大于中间元素，说明目标值应该插入在右半部分的起始位置，这个位置正好是中间元素的下一个位置；如果目标值小于中间元素，说明目标值应该插入在左半部分的末尾位置，这个位置正好是中间元素的位置。
代码实现
Java版本
public class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // 退出循环时，left > right，left 的位置就是可以插入 target 的位置 return left; } }
说明：
Java版本的实现中，我们定义了两个指针
left和right，分别表示数组的起始位置和结束位置。在while循环中，我们计算中间位置mid，并根据nums[mid]与目标值target的比较结果来更新left和right的值。最终，当循环结束时，left的值就是可以插入target的位置。
C语言版本
int searchInsert(int* nums, int numsSize, int target) { int left = 0, right = numsSize - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; }
说明：
C语言版本的实现与Java版本类似，但是需要注意在C语言中，数组的大小需要作为函数的参数传递。
Python3版本
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return left
说明：
Python3版本的实现也采用了二分查找的思路，并且使用了整数除法
//来避免浮点数。
Golang版本
package main import "fmt" func searchInsert(nums []int, target int) int { left, right := 0, len(nums)-1 for left <= right { mid := left + (right-left)/2 if nums[mid] ==target { return mid } else if nums[mid] < target { left = mid + 1 } else { right = mid - 1 } } return left } func main() { nums := []int{1, 3, 5, 6} target := 5 result := searchInsert(nums, target) fmt.Println(result) // 输出: 2 }
说明：
Golang版本的实现与前面几种语言类似，同样使用了二分查找算法来寻找目标值或者插入位置。
复杂度分析
- 时间复杂度：O(log n)，其中 n 是数组的长度。二分查找每次都将搜索范围减半，因此时间复杂度是对数级别的。
- 空间复杂度：O(1)。我们只使用了常量级别的额外空间来存储指针和中间变量。
方式二：线性搜索
思路
虽然题目中给出了数组是有序的，但我们也可以使用线性搜索（即遍历数组）的方式来解决问题。对于每个数组元素，我们比较它是否等于目标值，或者是否小于目标值以确定插入位置。
代码实现
Java版本
public class Solution { public int searchInsert(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] >= target) { return i; } } // 如果遍历完整个数组都没有找到目标值，说明目标值应该插入在数组末尾 return nums.length; } }
说明：
Java版本的实现中，我们遍历数组，一旦找到某个元素大于等于目标值，就返回当前位置。如果遍历完整个数组都没有找到，则返回数组长度，表示目标值应该插入在数组末尾。
C语言版本
int searchInsert(int* nums, int numsSize, int target) { for (int i = 0; i < numsSize; i++) { if (nums[i] >= target) { return i; } } return numsSize; }
说明：
C语言版本的实现与Java版本类似，但是需要注意在C语言中，数组的大小是作为函数的参数传递的。
Python3版本
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: for i in range(len(nums)): if nums[i] >= target: return i return len(nums)
说明：
Python3版本使用for循环遍历数组，一旦找到大于等于目标值的元素，就返回其索引。
Golang版本
package main import "fmt" func searchInsert(nums []int, target int) int { for i, num := range nums { if num >= target { return i } } return len(nums) } func main() { nums := []int{1, 3, 5, 6} target := 5 result := searchInsert(nums, target) fmt.Println(result) // 输出: 2 }
说明：
Golang版本的实现使用range关键字遍历数组，与Python3版本类似。
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。在最坏情况下，我们需要遍历整个数组才能找到插入位置。
- 空间复杂度：O(1)。我们同样只使用了常量级别的额外空间来存储索引和中间变量。
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 方式一（二分查找） | 效率高，时间复杂度低 | 需要数组有序 | O(log n) | O(1) |
| 方式二（线性搜索） | 代码简单，容易理解 | 时间复杂度较高 | O(n) | O(1) |
相似题目
| 相似题目 | 难度 | 链接 |
| leetcode 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 力扣-34 |
