Сложность: medium
Дан массив целых чисел nums, отсортированный в неубывающем порядке, найдите начальную и конечную позицию заданного целевого значения.
Если целевое значение не найдено в массиве, верните [-1, -1].
Вы должны написать алгоритм со временной сложностью O(log n).
Пример:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
👨💻 Алгоритм:
1⃣Определите функцию под названием findBound, которая принимает три аргумента: массив, целевое значение для поиска и булевое значение isFirst, указывающее, ищем ли мы первое или последнее вхождение цели.
Мы используем 2 переменные для отслеживания подмассива, который мы сканируем. Назовем их begin и end. Изначально begin устанавливается в 0, а end — в последний индекс массива.
2⃣Мы итерируем, пока begin не станет больше, чем end.
На каждом шаге мы вычисляем средний элемент mid = (begin + end) / 2. Мы используем значение среднего элемента, чтобы решить, какую половину массива нам нужно искать.
Если nums[mid] == target:
Если isFirst true — это означает, что мы пытаемся найти первое вхождение элемента. Если mid == begin или nums[mid - 1] != target, тогда мы возвращаем mid как первое вхождение цели. В противном случае мы обновляем end = mid - 1.
Если isFirst false — это означает, что мы пытаемся найти последнее вхождение элемента. Если mid == end или nums[mid + 1] != target, тогда мы возвращаем mid как последнее вхождение цели. В противном случае мы обновляем begin = mid + 1.
3⃣Если nums[mid] > target — мы обновляем end = mid - 1, так как мы должны отбросить правую сторону массива, поскольку средний элемент больше цели.
Если nums[mid] < target — мы обновляем begin = mid + 1, так как мы должны отбросить левую сторону массива, поскольку средний элемент меньше цели.
В конце нашей функции мы возвращаем значение -1, что указывает на то, что цель не найдена в массиве.
В основной функции searchRange мы сначала вызываем findBound с isFirst, установленным в true. Если это значение равно -1, мы можем просто вернуть [-1, -1]. В противном случае мы вызываем findBound с isFirst, установленным в false, чтобы получить последнее вхождение, а затем возвращаем результат.
😎 Решение:
func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
let firstOccurrence = findBound(nums, target, true)
if firstOccurrence == -1 {
return [-1, -1]
}
let lastOccurrence = findBound(nums, target, false)
return [firstOccurrence, lastOccurrence]
}
func findBound(_ nums: [Int], _ target: Int, _ isFirst: Bool) -> Int {
let N = nums.count
var begin = 0
var end = N - 1
while begin <= end {
let mid = (begin + end) / 2
if nums[mid] == target {
if isFirst {
if mid == begin || nums[mid - 1] != target {
return mid
}
end = mid - 1
} else {
if mid == end || nums[mid + 1] != target {
return mid
}
begin = mid + 1
}
} else if nums[mid] > target {
end = mid - 1
} else {
begin = mid + 1
}
}
return -1
}Ставь 👍 и забирай 📚 Базу знаний