题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
代码
int searchInsert(int* nums, int numsSize, int target){
int start = 0;
int end = numsSize - 1;
int mid = 0;
while(start <= end){
mid = (start + end)/2;
if(nums[mid] < target){
start = mid + 1;
}else if(nums[mid] > target){
end = mid - 1;
}else{
return mid;
}
}
return start;
}
执行结果
image.png
思路
通过二分查找方法查找元素的位置，可以大大加快执行的速度。
image.png
从上图可以看出，无论数组中元素的个数是奇数还是偶数的时候，当target<nums[mid]的时候，需要选取左边的区域。即另end = mid-1。当target>nums[mid]的时候，需要选取右边的区域，即另start = mid+1.
当target正好等于nums[mid]的时候，就找到了元素，直接返回下标mid即可。
需要考虑的一个特殊情况(即end<start，这个时候会跳出while循环)
当数组中的元素只剩下一个未判断的时候，并且这个元素并不等于target。
情况1(target < nums[mid] )
image.png
这个时候应当插入的位置对应的下标是start。
情况2(nums[mid] < target)
image.png
这个时候应当输入位置对应的下标同样是start。
所以，在while循环的外部，只需要return start即可。
