Двоичный поиск — один из самых важных алгоритмов в компьютерном мире. Это делает нашу жизнь намного проще, даже если мы этого не замечаем. Здесь, в этой статье, я объясняю бинарный поиск простыми словами, которые могут понять даже новички в CS. Я буду держать эту статью таким образом, чтобы она была очень краткой, но информативной. Приступим прямо сейчас!
Что такое бинарный поиск?
Двоичный поиск — это алгоритм поиска, используемый для поиска конкретной записи в наборе данных. Как правило, выпускники CS используют его для поиска определенного элемента поиска в массивах или любых других структурах данных. Я буду писать о бинарном поиске в отношении массивов, где они обычно используются.
Помните: бинарный поиск работает, только если информация или элемент отсортированы.
Псевдокод бинарного поиска
Возьмите два указателя start и end, каждый из которых указывает на первый и последний индекс элементов.
Пока (Начало ≤ Конец) {
Возьмите середину набора элементов.
if elementToBeSearched › middleElement -> Поиск справа или поиск слева.
if middleElement == elementToBeSearched -> Элемент найден!
}
если начало › конец -> Элемент не существует.
Это будет иметь место в порядке возрастания расположения. Для расположения в порядке убывания только то, что ниже, будет заменено выше.
if elementToBeSearched ‹ middleElement -> Поиск справа или поиск слева.
Нахождение среднего элемента
Мы можем найти средний элемент, выполнив классический Mid=(Start+End)/2. Но иногда емкость памяти типа данных языка программирования, да! Я говорю о Int, который может быть превышен, когда у нас есть большой объем данных, при выполнении Start+End.
Хорошей практикой было бы использовать выражение
Середина = (начало + (конец-начало) / 2 )
Это в основном то же выражение, что и предыдущее, если вы расширите его, но это гарантирует, что вы не так легко заполните емкость.
Но Ракеш… Зачем мне использовать двоичный поиск?
Бинарный поиск сокращает время, затрачиваемое на поиск определенного элемента по лоту. Сложность бинарного поиска в наихудшем случае составляет O(logN). Давайте возьмем пример и поймем, чтобы поместить это в контекст.
У вас есть 1 000 000 отсортированных записей. Вы хотите найти определенную запись. Линейный поиск в худшем случае должен будет выполнить 1 000 000 проверок, т. е. O (N), чтобы найти запись. Если мы предположим, что проверка записи занимает в среднем секунду, всего секунду, потребуется 11 дней и 14 часов, чтобы найти эту конкретную запись с помощью линейного поиска. Но если мы используем двоичный поиск, даже в худшем случае потребуется всего 20 проверок O(logN), чтобы найти запись, что займет всего 20 секунд, чтобы найти запись. Разве это не безумие?
Я прикрепляю ссылку на Java-код реализации бинарного поиска ниже.
*кашель* ботаник *кашель*… Но я знаю только, что массив отсортирован, но не в каком порядке. Что мне теперь делать?
Введите независимый от порядка двоичный поиск
Этот двоюродный брат, изучающий медицину бинарного поиска, представляет собой умную реализацию бинарного поиска, в которой вам не нужно знать, отсортирован ли массив по возрастанию или по убыванию.
Но откуда он знает?
Что ж, вы уже достаточно сообразительны, чтобы понять, что если мы возьмем любые два числа из массива в последовательности и сравним их, мы сможем узнать, в каком порядке расположены элементы.
1-й элемент › 2-й элемент -> По убыванию
1-й элемент‹ 2-й элемент -> По возрастанию
Но! и это большое, но что, если следующие соседние числа одинаковы? Поэтому, чтобы всегда быть уверенным, мы должны убедиться, что числа, которые мы берем для сравнения, являются первым и последним элементами.
Первый элемент › Последний элемент -> По убыванию
Первый элемент‹ Последний элемент → По возрастанию
Я прикрепляю ссылку на Java-код реализации бинарного поиска, не зависящего от порядка, ниже.
Я надеюсь, что это поможет вам понять бинарный поиск. Пишите мне по электронной почте с любыми предложениями, улучшениями или вопросами. Рад был помочь!
