Алгоритмы бинарного поиска: обзор, когда использовать и примеры

Данные настолько хороши, насколько хороши инструменты, используемые для их обработки и работы с ними. Когда вам приходится продираться через горы данных, вам нужны самые лучшие и эффективные методы, чтобы найти именно то, что вам нужно. Самый простой способ найти иголку в стоге сена — использовать магнит. Правильный алгоритм поиска это своего рода магнит, помогающий вам найти иголку нужных данных в (огромном, возвышающемся) стоге сена Больших данных!

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

Начнем с рассмотрения бинарного и линейного поиска.

Линейный подход к поиску

Линейный или последовательный поиск — это способ найти элемент в списке, последовательно просматривая элемент до тех пор, пока поиск не увенчается успехом. Конечно, существуют и другие, лучшие алгоритмы поиска, но линейные алгоритмы поиска легко настраивать и проводить, поэтому это достойный выбор, если список элементов (или массив) невелик.

Вот пример линейного поиска. Допустим, у вас есть десять ведер, пронумерованных от 1 до 10, и в одном из них лежит теннисный мяч. Вы начинаете с того, что смотрите в Ведро один и смотрите, есть ли там мяч. Если нет, то переходите к Ведру два и продолжайте в числовой последовательности, пока не найдете мяч. Это подход линейного поиска.

Итак, линейный поиск прост, и вы можете начать его с небольшой подготовкой или без нее. Это здорово, но это немного менее здорово, если у вас 1000 сегментов! Вот почему у нас есть бинарный поиск.

Посмотрите это видео, чтобы понять, что такое алгоритмы бинарного поиска и их применение в структурах данных.

Метод бинарного поиска

Двоичный поиск — это эффективный алгоритм, основанный на концепции «разделяй и властвуй», которая улучшает поиск путем рекурсивного деления массива пополам до тех пор, пока вы либо не найдете нужный элемент, либо список не сузится до одного фрагмента, который не соответствует нужному элементу.

Двоичный поиск работает по принципу использования отсортированной информации в массиве для снижения временной сложности до нуля (Log n). Вот основные шаги подхода бинарного поиска:

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

Когда использовать бинарный поиск

Вы удивитесь, узнав, что мы выполняем бинарный поиск каждый день нашей жизни? Двоичный поиск очень интуитивен и часто всплывает в реальной жизни. Мы обсудим некоторые примеры позже.

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

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

Есть много других ценных примеров, таких как тестирование кода, экзамены, собеседования при приеме на работу технических специалистов, задачи по коду и библиотечные задания.

Реализация бинарного поиска

Существует две формы реализации бинарного поиска: итеративные и рекурсивные методы. Наиболее существенное различие между двумя методами заключается в том, что рекурсивный метод имеет сложность пространства O(logN), тогда как итеративный метод использует O(1). Таким образом, хотя рекурсивную версию реализовать проще, итеративный подход более эффективен.

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

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

Вот пример итеративного алгоритма кодирования

класс BinarySearch

{

public static int binarySearchIterative(int() список, int первый, int последний, int ключ)

{

пока(первый <= последний)

{

int middle = first + (last – first) / 2;

если(список(середина) == ключ)

{

вернуться в середину;

}

иначе если(список(середина) < ключ)

{

первый = средний + 1;

}

еще

{

последний = средний – 1;

}

}

возврат -1;

}

публичный статический void main(String() args)

{

int() список = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44};

элемент int = 31;

int result = binarySearchIterative(список, 0, длина_списка – 1, элемент);

если(результат == -1)

{

System.out.println(“Элемент отсутствует в списке”);

}

еще

{

System.out.println(“Элемент найден по индексу: ” + result);

}

}

}

А вот пример рекурсивного алгоритма кодирования

класс BinarySearch

{

public static int binarySearchRecursive(int() список, int первый, int последний, int ключ)

{

если(первый >= последний)

{

возврат -1;

}

int middle = first + (last – first) / 2;

если(список(середина) == ключ)

{

вернуться в середину;

}

иначе если(список(середина) < ключ)

{

первый = средний + 1;

вернуть binarySearchRecursive(список, первый, последний, ключ);

}

еще

{

последний = средний – 1;

вернуть binarySearchRecursive(список, первый, последний, ключ);

}

}

публичный статический void main(String() args)

{

int() список = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44};

элемент int = 31;

int result = binarySearchRecursive(список, 0, длина списка – 1, элемент);

если(результат == -1)

{

System.out.println(“Элемент отсутствует в списке”);

}

еще

{

System.out.println(“Элемент найден по индексу: ” + result);

}

}

}

Оба примера кода были предоставлены любезно Повышение уровня кодирования.

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

Примеры бинарного поиска

Есть веская причина, по которой некоторые люди называют алгоритмы бинарного поиска «алгоритмами повседневной жизни». Даже если вы не работаете в сфере ИТ, можно с уверенностью сказать, что вы регулярно выполняли бинарный поиск. Это практически автоматически! Вот несколько повседневных примеров бинарного поиска.

Словари

Итак, вы каким-то образом оказываетесь без доступа в Интернет, и вам нужно найти определение слова «вомбат». Это значит вести себя как наши примитивные предки и тянуться к настоящему физическому словарю! Если вы хотите сделать линейный поиск, вы должны начать со слов на букву «А» и пройтись по словарю, пока не дойдете до слова «вомбат». Удачи вам в этом!

Однако большинство из нас умнее этого, и мы инстинктивно используем метод бинарного поиска. Мы просматриваем списки «W» и переходим в середину этого раздела. Если «wombat» по алфавиту меньше, чем слово на этой средней странице, мы игнорируем остальные страницы с правой стороны. Если «wombat» больше, то мы игнорируем левые страницы. Затем мы продолжаем повторять процесс, пока не найдем слово.

Поход в библиотеку

Вот еще одно применение, которое каким-то образом подразумевает отсутствие доступа к Интернету. Вы посещаете местную библиотеку, чтобы найти книгу под названием «Супы, которые я знал». Вы останетесь там навсегда, если войдете в библиотеку и будете искать на полках линейно. Поэтому вместо этого вы полагаетесь на алфавитный порядок или систему кодов, например, на десятичную систему Дьюи, чтобы сузить свой поиск.

Номера страниц

Итак, вы нашли «Супы, которые я знал» и взяли их в библиотеке. Друг сказал вам, что на странице 200 есть фантастический суп. Поэтому вы не открываете книгу на предисловии и не начинаете перелистывать страницы, продвигаясь к 200! Вместо этого вы открываете книгу наугад и проверяете номер страницы (мы предполагаем, что в этой книге нет оглавления!). Если номер страницы больше 200, то ваш суп находится слева от текущей страницы. Однако, если номер страницы меньше 200, вы переходите к страницам справа. Вы продолжаете делать это, пока не найдете страницу 200.

Этот пример, вероятно, самый распространенный, и большинство из нас делают это, даже не задумываясь.

Итак, независимо от того, работаете ли вы аналитиком данных и пытаетесь реализовать алгоритмы, или просто среднестатистический человек, далекий от ИТ, который любит читать, но по какой-то причине не имеет доступа к Интернету, алгоритмы бинарного поиска — это то, что вам нужно!

Хотите узнать больше об алгоритмах структурирования данных?

Алгоритмы активно используются во многих ИТ-профессиях, которые сосредоточены на анализе и обработке данных. Если вы рассматриваете новую карьеру в области анализа данных или смежной области, вам следует ознакомиться с алгоритмами. Это может даже иметь решающее значение, когда вы ищете работу в этих областях!

Simplilearn предлагает бесплатный онлайн-курс «Введение в алгоритмы сортировки». В ходе этого курса вы изучите различные типы сортировки, основные концепции сортировки и то, почему они необходимы. После завершения этого курса у вас будет четкое представление о сортировке пузырьком, двоичном поиске, быстрой сортировке и многих других алгоритмах с помощью соответствующих практических примеров.

Вы узнаете:

• Основы сортировки структур данных
• Как выбрать подходящий алгоритм для разных сценариев
• Как работать с различными типами алгоритмов сортировки

Этот курс идеально подходит для:

Итак, загляните на Simplilearn и улучшите свои навыки. Кто знает? Может быть, после изучения алгоритмов вы сможете пройти один из более интенсивных курсов, которые являются продолжением бесплатного курса, например, Data Scientist или Data Analyst. Посетите Simplilearn сегодня!