【Day 27 】2021-06-05 - 35. 搜索插入位置
题目描述
35. 搜索插入位置
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/search-insert-position
前置知识
暂无
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
我的回答
解法一
时空复杂度
时间复杂度：O(n)
空间复杂度: O(1)
var searchInsert = function (nums, target) {
let ans = 0
while (nums[ans] < target) {
ans++
}
return ans
};
解法二
时间复杂度：O(logn)
空间复杂度: O(1)
二分法
var searchInsert = function (nums, target) {
let left = 0
let right = nums.length - 1
while (left <= right) {
let mid = (left + right) >> 1
if (nums[mid] < target) {
left = mid + 1
} else if (nums[mid] > target) {
right = mid - 1
} else {
return mid
}
}
return left
};