Двоичный поиск найдите верхнюю и нижнюю границы с помощью OnePunch The Startup Medium

Двоичный поиск — найти верхнюю и нижнюю границы.

В этом посте будет представлено одно конкретное применение двоичного поиска, то есть, когда вас просят найти верхнюю или нижнюю границу, или, точнее, когда вам нужно найти максимум наименьшего значения или минимум наибольшего значения. .

Двоичный поиск — это алгоритм поиска цели в отсортированном массиве. Он выбирает средний элемент в массиве и сравнивает его с целевым; если они не равны, он удаляет одну половину массива и продолжает поиск другой половины таким же образом (Википедия).

Самое простое его применение — найти число или позицию в массиве. Некоторые практики можно найти на Leetcode:

Другой популярный случай, когда вас просят найти максимум наименьшего значения или минимум наибольшего значения. Возьмем 410. Наибольшая сумма разбиения массива из Leetcode в качестве примера, чтобы проиллюстрировать, как справляться с такого рода проблемами..

Как искать.

Пространство поиска будет от максимума входных чисел, когда m = len (nums), до суммы чисел, когда m = 1 .

Каждый раз мы выбирали средний элемент в середине области поиска в качестве нашего порога и вычисляли количество подсчетов подмассивов, следя за тем, чтобы сумма каждого подмассива не превышала середину. Если посчитать>m, это означает, что мы должны увеличить mid, чтобы уменьшить количество подмассивов; иначе, если count, это означает, что мы можем уменьшить mid, чтобы увеличить количество подмассивов, но mid все еще квалифицируется.

Итак, псевдокод:

Как выбрать середину, l и r.

Выберите середину.

Выбирая середину из нечетного количества элементов, мы можем найти средний; когда количество элементов четное, есть два способа выбрать: первый или второй..

Оба они работают, но должны соответствовать тому, как мы работаем с l и r. Когда мы выбираем первый, используя l + (r-l) // 2, мы хотим избежать l = mid, потому что это может привести к бесконечному циклу. Например, когда есть два элемента [0,1] и mid = 0, тогда l становится mid, и итерация повторяется снова и снова..

Точно так же, когда мы выбираем последний, используя r- (r-l) // 2, мы хотим избежать r = mid .

Присвоение значений l и f.

Итак, будем ли мы присвоить значения l и r ?

Это зависит от контекста!

Нижняя граница.

Например, когда в вопросе задается нижняя граница, если mid работает, тогда r должно быть mid, а не mid-1, потому что mid может быть ответом! И когда mid не работает, l должно быть mid + 1, потому что мы уверены, что mid не является ответом, и все, что падает на одну середину слева, тоже не сработает..

Верхняя граница.

Точно так же мы можем присвоить значения l и r, как показано ниже..

Одним словом, то, как мы выбираем mid и присваиваем значения l и r, определяется тем, что мы ищем: нижняя граница или верхняя граница..

Наконец, нам нужно реализовать функцию подсчета, и вот код AC.

Практики.

В Leetcode вы можете найти следующие практики:

Стартап.

Станьте умнее в создании своего дела. Присоединяйтесь к The Startup: более 782 тысяч подписчиков.

Похожие статьи