Написано: 09.03.2023
35. Найти позицию вставки (Search Insert Position)
Задание.
Дан отсортированный массив целых чисел nums и значение target
Нужно вернуть индекс, если target найден. Если target не найден, нужно вернуть индекс, куда бы он был вставлен при вставке по порядку.
Нужно написать алгоритм со сложностью времени выполнения O(log n).
Пример 1.
Входные данные: nums = [1,3,5,6], target = 5
Результат: 2
Пример 2.
Входные данные: nums = [1,3,5,6], target = 2
Результат: 1
Пример 3.
Входные данные: nums = [1,3,5,6], target = 7
Результат: 4
Решение.
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int s, e = nums.size() - 1, index, m;
s = index = 0;
while(s <= e) {
m = s + (e - s)/2;
if(nums[m] == target) { // найден
index = m; // запоминаем, выходим
break;
} else if(target < nums[m]) { // справа больше, чем нужно
e = m - 1; // отсекаем правую половину
} else {
// слева меньше, чем нужно
// отсекаем левую половину
s = index = m + 1;
}
}
return index;
}
};