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

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

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

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

Подход линейного поиска

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

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

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

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

Подход двоичного поиска

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

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

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

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

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

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

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

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

Реализация двоичного поиска

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

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

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

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

класс БинарныйПоиск

{

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

{

пока (первый

{

int middle = первый + (последний — первый)/2;

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

{

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

}

иначе, если (список (средний)

{

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

}

еще

{

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

}

}

вернуть -1;

}

public static void main(String() args)

{

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

int элемент = 31;

int result =binarySearchIterative(list, 0, list.length – 1, element);

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

{

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

}

еще

{

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

}

}

}

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

класс БинарныйПоиск

{

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

{

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

{

вернуть -1;

}

int middle = первый + (последний — первый)/2;

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

{

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

}

иначе, если (список (средний)

{

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

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

}

еще

{

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

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

}

}

public static void main(String() args)

{

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

int элемент = 31;

int result =binarySearchRecursive(list, 0, list.length – 1, element);

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

{

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

}

еще

{

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

}

}

}

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

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

Примеры двоичного поиска

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

Словари

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

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

Идем в библиотеку

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

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

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

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

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

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

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

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

Вы узнаете:

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

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

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