leetcode 35. 搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/

题目

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

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

示例

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

提示

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

解一：二分查找

思路

维护三个指针l,r,m
初始化l和r在数组首尾
循环：当l<r时
m取(l+r)/2向下取整

• 如果target<nums[m],r-m-1
• 如果nums[m]<target,l=m+1
  循环结束时l=r，比较target和nums[l]
• 等于，命中，返回l
• 小于，插入到l的位置，返回l
• 大于，插入到l右边，返回l+1

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let l=0,r=nums.length-1;
    let m=parseInt((l+r)/2);
    if(nums[l]>target) return 0;
    if(nums[r]<target) return r+1;
    while(l<r){
        m=parseInt((l+r)/2);
        if(target<=nums[m]) r=m-1;
        else l=m+1;
    }
    return nums[l]>=target?l:l+1;
};

复杂度分析

时间复杂度$O(\log n)$

解二：直接遍历

思路

直接遍历数组，因为是升序排序的

• 直接命中，返回索引
• 找到第一个比target大的元素，返回索引
• 没找到，加在后面，返回数组长度

代码

var searchInsert = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return nums.length;
};

时间复杂度分析

$O(n)$