10 · МОНОТОННОСТЬ

Бинарный поиск

Ищи первую позицию, где монотонный предикат становится истинным.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Полуинтервал

left, right := 0, len(nums)
for left < right {
    mid := left + (right-left)/2
}

[left, right) уменьшает число особых случаев.

Стандартная библиотека

i := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= target
})

sort.Search реализует поиск первой true-позиции.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Lower bound

Первая позиция со значением не меньше target.

O(log n) time · O(1) space

solution.go

func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target { left = mid+1 } else { right = mid }
    }
    return left
}

ПРИМЕР РЕШЕНИЯ

Минимальная скорость

Бинарный поиск по ответу.

O(n log maxPile) time · O(1) space

solution.go

func minEatingSpeed(piles []int, hours int) int {
    left, right := 1, slices.Max(piles)
    for left < right {
        speed := left + (right-left)/2
        used := 0
        for _, pile := range piles { used += (pile+speed-1)/speed }
        if used <= hours { right = speed } else { left = speed+1 }
    }
    return left
}

ПРИМЕР РЕШЕНИЯ

Поиск вставки

Lower bound одновременно находит элемент и позицию для его вставки.

O(log n) time · O(1) space

solution.go

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target { left = mid+1 } else { right = mid }
    }
    return left
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Сформулируй монотонный предикат
Докажи, какая граница возвращается
Избегай mid := (left+right)/2 при больших int