Бинарный поиск (Binary Search)

Предлагаю сначала разобрать подход, потом решить задачу на сам бинарный поиск, а затем решить ещё одну задачу уровня Medium, где бинарный поиск нам тоже пригодится. Разберём как обычно на примерах, с картинками и кодом, чтобы в голове точно улеглись все нюансы.

Пример

Представьте, что друг задумал число от 1 до 50, а нам нужно его угадать. Когда мы будем предлагать варианты, друг будет отвечать "больше/меньше" или "угадал".

Как будем действовать?

Брутфорс

Да просто начнем с 1 и будем перечислять 1, 2, 3 и так далее, пока не угадаем. В худшем случае придется перебрать все числа. То есть сложность по времени будет O(n).

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

В случае брутфорса мы не использовали подсказки друга про "больше/меньше". Если бы он отвечал нам просто "нет" на наше перечисление, в решении ничего бы не изменилось, мы также перечислили бы все числа.

Бинарный поиск использует эти подсказки.

Определим сразу число в середине — 25 и предложим его другу.

Если он ответит "меньше", значит теперь нам нужно угадывать в диапазоне от 1 до 24.

Если он ответит "больше", значит продолжим в диапазоне от 26 до 50.

То есть мы всего одним ответом отсекли половину неправильных вариантов.

— 25
— Меньше

Повторяем действие для диапазона 1 - 24:

— 12
— Больше.

Значит диапазон для поиска стал 13 - 24. На каждом шаге мы отсекаем половину вариантов и пробуем снова, пока не придем к ответу.

Для чисел от 1 до 50 с помощью бинарного поиска мы угадаем задуманное число максимум за 6 шагов.

log 50 находится между 5 и 6, так как 2^5 = 32 и 2^6 = 64

Бинарный поиск на литкоде

#704. Binary Search

Дан массив чисел nums[ ], отсортированный по возрастанию, и число target, которое нужно найти и вернуть его индекс в массиве. Если не найдем, вернуть -1.

Важно! Бинарный поиск можно применять к массиву только если он отсортирован.
Иногда в задаче можно самому вызвать функцию сортировки, если видите, что это нужно и нет требования уложиться в O(n), так как сортировка имеет сложность O(n*log n).

Определим два указателя на первом и последнем индексах. Они будут обозначать границы нашего диапазона поиска. Изначально они охватывают весь массив.

В цикле, пока указатели не пересекутся:

Определяем серединку.

Это можно сделать как (left + right) / 2, но в некоторых языках в случае огромнейшего массива на дальнейших шагах может быть переполнение числовой переменной, поэтому в них безопаснее использовать следующий подход определения индекса центрального элемента:

mid = left + (right - left) / 2

Проверяем, если nums[mid] меньше target, значит мы можем отбросить всю левую часть, так как все элементы в левой части тоже меньше target (потому что массив отсортирован по возрастанию). Раз мы отбрасываем всю левую часть, то можем сдвинуть левую границу на элемент после mid:

left = mid + 1

Почему сдвигаем left на mid + 1, а не на сам mid? Потому что мы уже проверили, что nums[mid] меньше target, а не равен ему, значит сам mid не подходит, зачем же нам гарантированно неправильный вариант оставлять в диапазоне поиска.

Если nums[mid] больше target, значит мы можем отбросить всю правую часть, так как все элементы в правой части тоже больше target и соответственно не подходят. Раз мы отбрасываем всю правую часть, то можем сдвинуть правую границу на элемент перед mid:

right = mid - 1

Аналогично, почему сдвигаем right не на сам mid: мы уже знаем, что nums[mid] больше target, а не равен ему, значит и этот mid не подходит.

Продолжаем, пока не найдем nums[mid], равный target.

Возвращаем найденный индекс mid.

Готово, вы великолепны!

Итоговый код

На Python:

def search(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + ((right - left) // 2)

        if nums[mid] > target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            return mid
    return -1

На Java:

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2 ;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

На Go:

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

Поиск минимального элемента в повернутом массиве

Теперь предлагаю разобрать задачу сложнее, уровня Medium:

#153. Find Minimum in Rotated Sorted Array

Дан отсортированный по возрастанию массив из уникальных элементов, который был повернут (rotated) от 1 до n раз.

Что значит повернут?

В примере выше отсортированный массив [-1, 0, 3, 5, 8, 12] был повернут 4 раза:

• [12, -1, 0, 3, 5, 8]
• [8, 12, -1, 0, 3, 5]
• [5, 8, 12, -1, 0, 3]
• [3, 5, 8, 12, -1, 0]

Нам нужно вернуть самый минимальный элемент из такого массива.

Сложность по времени должна быть O(log n), поэтому просто перебрать все элементы в поисках минимума не подойдет.

Заданная сложность O(log n) и теги задачи 😄 намекают, что стоит использовать бинарный поиск.

Для разбора решения предлагаю взять массив побольше:

Основная трудность состоит в том, что мы не можем использовать бинарный поиск "в лоб", ведь массив не отсортирован по возрастанию: при повороте массива самые маленькие элементы слева уехали вправо.

Можно сказать, что наш массив теперь состоит их двух отсортированных по возрастанию подмассивов:

Заведем переменную для хранения минимума currMin и два указателя на границах массива: left и right. Будем действовать в цикле, пока указатели не пересекутся.

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

Если же мы увидели, что левый элемент больше, чем самый правый значит массив был повернут не в исходное положение, и более маленькие элементы уехали вправо. Значит минимум нам нужно искать в правом подмассиве. Искомым для нас будет первый (самый левый) элемент правого подмассива.

Но где граница между правым и левым подмассивом? Как искать этот первый элемент?

Используем бинарный поиск.

Определим средний элемент и сравним его с текущим минимумом. Если он меньше текущего минимума, то обновим значение текущего минимума.

Сравним средний элемент с самым левым. Если средний элемент больше самого левого элемента (или равен*), значит он является частью отсортированного по возрастанию левого подмассива. А нам не нужен левый подмассив, наш искомый элемент в правом подмассиве. Поэтому всё, что слева от текущего mid отбрасываем. Для этого передвигаем left направо от mid:

left = mid + 1

*Почему больше или равен? В массиве все элементы уникальны, но если осталось только 2 элемента, то left и mid будут указывать на один и тот же элемент.

Передвинув указатель, переходим на новый шаг цикла.

Первым делом проверяем: левый элемент меньше, чем правый? Если да, значит оба указателя уже в правой части массива, можно обновлять currMin и выходить из цикла. Если нет, значит продолжаем бинарный поиск.

Снова определим средний элемент и сравним его с текущим минимумом.

Сравним средний элемент с самым левым. Если средний элемент меньше самого левого элемента, значит mid уже в правом подмассиве. Мы ищем самый первый (самый левый) элемент правого подмассива, поэтому всё, что справа от текущего mid мы отбрасываем. Для этого передвигаем right:

right = mid - 1

Передвинув указатель, переходим на новый шаг цикла.

Первым делом проверяем: левый элемент меньше, чем правый? Если нет, значит продолжаем бинарный поиск.

Определим средний элемент и сравним его с текущим минимумом.

Сравним средний элемент с самым левым. Если он больше самого левого (или равен) значит средний элемент является частью отсортированного по возрастанию левого подмассива. Наш искомый элемент по-прежнему в правом подмассиве, поэтому всё, что слева от текущего mid отбрасываем. Для этого передвигаем left направо от mid:

left = mid + 1

Передвинув указатель, переходим на новый шаг цикла.

Первым делом проверяем: левый элемент меньше, чем правый?

Да! Теперь это условие выполнено. Значит оба указателя уже в правой части массива, сравниваем значение левого элемент с текущим минимумом, при необходимости обновляем его и выходим из цикла.

Готово! В переменной currMin будет лежать минимальное значение массива.

Иногда массив может быть устроен так, что указатель left не попадет на минимальный элемент, а на него попадет сам mid. Это тоже будет работать, потому что средний элемент мы на каждом шаге сравниваем с currMin и при необходимости обновляем его. Если mid попадет на самый маленький элемент массива, то его значение сохранится в currMin. Алгоритм пойдет дальше, пока left не станет больше right. Тогда мы выйдем из цикла, а в currMin так и будет лежать тот самый найденный минимум.

Итоговый код

На Python:

def findMin(self, nums: List[int]) -> int:
    currMin = nums[0]
    left, right = 0, len(nums) - 1
    
    while left <= right:
        if nums[left] < nums[right]:
            currMin = min(currMin, nums[left])
            break

        mid = left + (right - left) // 2
        currMin = min(currMin, nums[mid])
        if nums[mid] >= nums[left]:
            left = mid + 1
        else:
            right = mid - 1
    return currMin

На Java:

public int findMin(int[] nums) {
    int currMin = nums[0];
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        if (nums[left] < nums[right]) {
            currMin = Math.min(currMin, nums[left]);
            break;
        }

        int mid = left + (right - left) / 2;
        currMin = Math.min(currMin, nums[mid]);
        if (nums[mid] >= nums[left]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return currMin;
}

На Go:

func findMin(nums []int) int {
  currMin := nums[0]
  left, right := 0, len(nums)-1

  for left <= right {
    if nums[left] < nums[right] {
      if nums[left] < currMin {
        currMin = nums[left]
      }
      break
    }

    mid := left + (right-left)/2
    if nums[mid] < currMin {
      currMin = nums[mid]
    }
    if nums[mid] >= nums[left] {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return currMin
}

Надеюсь, было полезно! ❤️