【刷题笔记】搜索插入位置（二分法的活用）

题目：

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

请必须使用时间复杂度为 O(log 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
 

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的 升序 排列数组
-104 <= target <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-insert-position

        首先，明确要求使用时间复杂度为O(log n)的算法，所以我这里选择二分法。（因为是排好序了的）

解法：

        首先明确二分法在有顺序的数组里面是如何进行筛选的：先找中间的那个数，找到了返回中间的下标。否则如果比中间的数要大，那么区间就变到了右边去找，小就去左边区间取中去找。知道区间缩短为0或者1为止。

        但是此题如果只是用上面的普通二分查找是不行的。因为此时还有一个如果找不到就需要返回下标的要求。

        所以，我们就需要一个不确定的状态。在将该数组有数的前提下排除在外，那么此数应该就是在比其大的那个数的下标进行排序，往前就应该比其小了。（如果target比全数组所有数大应该当做特殊情况）那么，直到循环结束，此端点也就是我们要找的那个下标。

        上述的意思也就是：targe如果比mid所在数大，那么，此时的[begin, end]一定没有符合其插入的位置，反之，如果targe比mid所在数小于或者等于，那么[begin, end]就存在着符合其插入的位置，正好就是end。所以，代码如下：

int searchInsert(int* nums, int numsSize, int target) {
    if (nums[numsSize - 1] < target)
        return numsSize;
    int begin = 0;
    int end = numsSize - 1;
    while (begin < end)
    {
        int middle = begin + (end - begin) / 2;
        if (nums[middle] < target)
        {
            begin = middle + 1;
        }
        else
        {
            end = middle;
        }
    }
    return end;
}