Дан массив nums, отсортированный в неубывающем порядке, и целое число target. Необходимо найти индекс, на который можно вставить target, чтобы сохранить порядок сортировки массива.
Пример 1:
Ввод: nums = [0,0,1,1,1,3,3,5,8], target = 2 Вывод: 5
Пример 2:
Ввод: nums = [0,0,1,1,1,3,3,5,8], target = 4 Вывод: 7
Ограничения:
len(nums) >= 1public class Solution {
public static int SearchInsertIndex(List<int> nums, int target) {
int l = 0, r = nums.Count;
while (r - l > 1) {
int m = (l + r) / 2;
if (nums[m] <= target) {
l = m;
}
else {
r = m;
}
}
if (nums[l] >= target) {
return l;
}
return r;
}
}#include <vector>
using namespace std;
int searchInsertIndex(vector<int> nums, int target) {
int l = 0, r = nums.size();
while (r - l > 1) {
int m = (l + r) / 2;
if (nums[m] <= target) {
l = m;
} else {
r = m;
}
}
if (nums[l] >= target) {
return l;
}
return r;
}package main
func searchInsertIndex(nums []int, target int) int {
l, r := 0, len(nums)
for r-l > 1 {
m := (l + r) / 2
if nums[m] <= target {
l = m
} else {
r = m
}
}
if nums[l] >= target {
return l
}
return r
}import java.util.*;
public class Solution {
public Integer searchInsertIndex(List<Integer> nums, Integer target) {
int l = 0, r = nums.size();
while (r - l > 1) {
int m = (l + r) / 2;
if (nums.get(m) <= target) {
l = m;
} else {
r = m;
}
}
if (nums.get(l) >= target) {
return l;
}
return r;
}
}from typing import *
def search_insert_index(nums: List[int], target: int) -> int:
l, r = 0, len(nums)
while r - l > 1:
m = (l + r) // 2
if nums[m] <= target:
l = m
else:
r = m
if nums[l] >= target:
return l
return r/**
* @param {number[]} nums
* @param {number} target
* @returns {number}
*/
export function searchInsertIndex(nums, target) {
let l = 0, r = nums.length;
while (r - l > 1) {
const m = Math.floor((l + r) / 2);
if (nums[m] <= target) {
l = m;
} else {
r = m;
}
}
return nums[l] >= target ? l : r;
}Оценка сложности
O(log(n)), где n - длина массива numsO(1)