目录

题目要求

代码实现

---

题目要求

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
请必须使用时间复杂度为 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)