LeetCode 35. 搜索插入位置_.leetcode 35. 搜索插入位置

题目描述：

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法思路：

这个题目要求了时间复杂度，所以无脑遍历（我最喜欢的方法）显然不行了，相信有经验的小伙伴已经想到了用二分查找法，那么就用两个指针，left和right,再设置一个变量mid=（left+right）/2，

这样的先初始话left=0,right=数组长度-1，然后判断mid下标对应的数组元素与目标值target的关系，如果小于目标值那么就让left=mid+1,如果大于目标值就让right=mid-1,如果等于那么就直接返回对应下标，然后重复进行此操作，直到left>right,因为题中有另一种要求就是如果不存在这个值就返回插入位置，实际上也是一样的，可能看到这个要求会感觉题变难了，以为不能用二分法。 

代码段：

//nums是数组，numsSize是数组大小，target是目标值
int searchInsert(int* nums, int numsSize, int target)
{
	int left = 0, right = numsSize - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] > target)
			right = mid-1;
		else if (nums[mid] < target)
			left = mid + 1;
		else
			return mid;
	}
	return left;//个人感觉可能就这里可能会有些不理解，实际上如果你在纸上试试就会发现其中的奥秘。
}

看到这里就结束了，代码写的不好，思路可能也不够清晰，希望大家能够谅解。一起刷题吧。