35. Search Insert Position 搜索插入位置

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

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

You must write an algorithm with O(log n) runtime complexity.

请必须使用时间复杂度为 O(log n) 的算法。

Example 1:示例 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

输入: nums = [1,3,5,6], target = 5
输出: 2

Example 2:示例 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

输入: nums = [1,3,5,6], target = 2
输出: 1

Example 3:示例 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

输入: nums = [1,3,5,6], target = 7
输出: 4

Constraints:提示:

1 <= nums.length <=
- <= nums[i] <=
nums contains distinct values sorted in ascending order.

• nums 为 无重复元素 的 升序 排列数组

- <= target <=

 

 

 

 

C语言：

int searchInsert(int* nums, int numsSize, int target){
    int index=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]<target)
        {
            if(i+1==numsSize)
            {
                index=i+1;
                break;
            }
            else if(nums[i+1]>=target)
            {
                index=i+1;
                break;
            }
        }
        else if(nums[i]==target)
        {
            index=i;
            break;
        }
    }
    return index;
}

执行结果：通过

执行用时：4 ms, 在所有 C 提交中击败了94.53%的用户

内存消耗：5.7 MB, 在所有 C 提交中击败了97.52%的用户

通过测试用例：64 / 64

从《二分查找》上，学到了二进制数，向右移一位是除以2的数，向左移一位是乘以2的数。

C语言：

int searchInsert(int* nums, int numsSize, int target){
    int left=0,right=numsSize-1,index=numsSize;
    while(left<=right)
    {
        int mid=((right-left)>>1)+left;
        if(target<=nums[mid]){
            index=mid;
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    return index;
}

执行结果：通过

执行用时：4 ms, 在所有 C 提交中击败了94.53%的用户

内存消耗：5.8 MB, 在所有 C 提交中击败了69.62%的用户

通过测试用例：64 / 64