目录
题目要求
代码实现
题目要求
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
请必须使用时间复杂度为 O(long n) 的算法
示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4
代码实现
代码演示：
int searchInsert(int* nums, int numsSize, int target)
{int left = 0;int right = numsSize - 1;int mid = 0;while (left <= right){mid = (left + right) / 2;if (nums[mid] > target){right = mid - 1;}else{left = mid + 1;}}return left;
}代码解析：
题目要求时间复杂度为 O(long n) ，那么就要使用二查找法，每次去掉一半的值
创建 left 和 right 两个指针，依次往中间排除，while 循环结束后，left 的值就是要插入的 target 元素的下标
代码验证：
当 target 为最小值时：
当 target 为中间值时：
当 target 为最大值时：
算法的时间和空间复杂度：
while 循环是二分查找法，经典的 O(long n) ，且没有消耗额外的空间，得出：
时间复杂度：O(long n)
空间复杂度：O(1)