35. 搜索插入位置

题目描述

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

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

示例 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即可。