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

Reference

题解¶

使用二分查找。

设数列\(\{a_i\}\)为升序数列，目标值\(b\)的插入位置\(j\)满足：

\(b \leq a_j\)
\(b > a_{j - 1}\)

注意本题要求的数据与普通二分查找的返回值的意义不同。

二分查找返回最后一个不大于目标值的元素下标。
本题要求返回第一个不小于目标值的元素下标。

int bSearch(int *nums, int lo, int hi, int target)
{
    int mid;
    while (lo < hi)
    {
        mid = (lo + hi) >> 1;
        if (nums[mid] >= target)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

int searchInsert(int* nums, int numsSize, int target){
    return bSearch(nums, 0, numsSize, target);
}

附：二分查找算法，供比较

int bSearch(int *nums, int lo, int hi, int target)
{
    int mid;
    while (lo < hi)
    {
        mid = (lo + hi) >> 1;
        if (nums[mid] > target)
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo - 1;
}

在二分查找中，始终有：

nums[lo - 1] 是截至当前已确认的不大于target的最大元素
nums[hi] 是截至当前已确认的大于target的最小元素

而在本题算法中，始终有：

nums[lo - 1] 是截至当前已确认的小于target的最大元素
nums[hi] 是截至当前已确认的不小于target的最小元素

原因在于，两算法对等于的情况的处理不同，二分查找对nums[mid] == target情况的处理为 lo = mid + 1，仅当nums[mid] > target时才执行hi = mid。由于[lo, hi)是当前已确认的区间，则nums[hi]为已确认的大于target的最小元素，而nums[lo - 1]为不大于 target的最大元素。而本题算法对nums[mid] == target情况的处理为hi = mid，仅当 nums[mid] < target时才执行lo = mid + 1，则nums[hi]为已确认的不小于target的最小元素，nums[lo - 1]为已确认的小于target的最大元素。

35. 搜索插入位置¶

题目¶

题解¶

评论