LeetCode 搜索插入的位置

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

你可以假设数组中无重复元素。

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

思路分析：第一反应当然是想到用二分查找法，但是此题如果是容器中不含这个元素，二分法就有些无能为力。但是我觉得二分法的精髓在于区间的缩小，当我们改变它的趋近速度，在未找到时，使它推出的时候左区间下标和右区间下标相同。代码如下

int searchInsert(vector<int>& nums, int target) {
	int numsSize = nums.size();
	if (numsSize == 0){
		return 0;
	}
	int begin = 0;//起始下标
	int end = numsSize - 1;//终止下标
	while (begin <= end){
		int mid = (begin + end) / 2;
		if (nums[mid] == target){
			return mid;
		}
		else if (begin == end){//①精简的二分法需要删除这个if判断
			break;
		}
		else if (nums[mid] < target){
			begin = mid + 1;//②这里是关键
		}
		else {
			end = mid;//③这里是关键
		}
	}
	//上面的while退出时，必定是begin==end，或者找到了targe直接返回了
	if (nums[begin] > target){//插在begin之前
		return begin;
	} 
	else {//begin之后
		return begin + 1;
	}
}

假设nums容器中没有target，那么最后必定会出现begin与end相邻的情况，此时mid= （begin + end），计算后mid仍然为begin，接着必定会选择②或者③中的其中一步进行下一步的缩减。不管选择哪一个都是将begin = = end。

时间复杂度O（log n），至于为啥上面的while退出时必定是begin == end，我解释不太来。我是经过好多次尝试，才将标了序号的位置修改到了希望达到的效果。如果实在不清楚的话，可以在纸上模拟区间的逼近过程

翻阅评论区，发现了一种比较思路比较简单粗暴的方法。

虽说近似暴搜，但还是写出来了。