Линейный поиск против бинарного поиска: разница между линейным поиском и бинарным поиском

Опубликовано: 2021-02-09

Оглавление

Введение

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

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

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

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

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

Временная сложность последовательного поиска линейна O(n), а временная сложность бинарного поиска (пример интервального поиска) равна O(log n). Кроме того, существуют другие алгоритмы поиска, такие как экспоненциальный поиск, поиск с переходом и т. д.

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

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

Линейный поиск

Как уже говорилось, алгоритм линейного поиска сравнивает каждый элемент массива, и вот код для этого.

открытый класс UpGrad {
 public static int linear_search ( int [] arr, int n, int k) {
 для ( int i= 0 ; i<n; i++)
 если (обр[i]==k)
 вернуть я+ 1 ;
 возврат – 1 ;
 }
 public static void main (String [] args) {
 int [] arr = новый int [] { 1 , 2 , 5 , 6 , 3 , 8 , 9 , 9 , 0 , 13 , 45 , 65 };
 интервал к = 13 ;
 int n=arr.length;
 int r=linear_search(arr, n, k);
 если (г==- 1 )
 System.out.println ( «элемент не найден» );
 еще
 System.out.println( "Найден элемент в позиции " +r+ "" );
 }
 }

Давайте пройдемся по коду.

Мы объявили функцию linear_search, которая ожидает массив, целочисленный ключ в качестве параметров. Теперь нам нужно перебрать все элементы и сравнить, совпадает ли он с нашим ключом поиска, поэтому мы написали цикл for, который перебирает массив, а внутри него есть цикл if, который проверяет, соответствует ли число в этой позиции. с ключом поиска или нет. Если мы найдем совпадение, мы вернем позицию. Если такого элемента в массиве нет, то мы вернем -1 в конце функции.

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

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

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

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

открытый класс UpGrad {
 public static int binary_search ( int [] arr, int k) {
 int l= 0 ,h=arr.length- 1 ,mid= 0 ;
 в то время как (л <= ч) {
 середина=l+(hl)/ 2 ;
 если (обр[середина]==k)
 вернуть середину+ 1 ;
 иначе , если (обр[середина]>k)
 h=середина 1 ;
 еще
 л=середина+ 1 ;
 }
 возврат – 1 ;
 }
 public static void main (String [] args) {
 int [] arr = новый int [] { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 };
 интервал к = 8 ;
 int r = двоичный_поиск (обр, к);
 если (г==- 1 )
 System.out.println ( «элемент не найден» );
 еще
 System.out.println( "Найден элемент в позиции " +r+ "" );
 }
 }

Давайте пройдемся по коду.

Мы объявили метод binary_search, который ожидает отсортированный целочисленный массив и целочисленный ключ в качестве параметров. Мы инициализируем переменные low, high, mid. Здесь low, high — это указатели, где low будет иметь индекс 0, а high — индекс n в начале. Так как же работает бинарный поиск?

Сначала посчитаем середину минимума и максимума. Мы можем вычислить среднее значение как (низкое+высокое)/2, но иногда высокое значение может быть большим числом, и добавление низкого значения к высокому может привести к целочисленному переполнению. Таким образом, расчет середины как low+(high-low)/2 был бы оптимальным способом.

Мы сравним элемент в середине с ключом поиска и вернем индекс, если найдем совпадение. В противном случае мы проверим, больше ли средний элемент ключа или меньше ключа. Если среднее значение больше, то нам нужно проверить только первую половину массива, потому что все элементы во второй половине массива больше ключа, поэтому мы обновим высокое значение до середины-1.

Точно так же, если mid меньше ключа, нам нужно искать во второй половине массива, следовательно, обновлять low до mid+1. Помните, что бинарный поиск основан на алгоритме уменьшения и завоевания, поскольку мы игнорируем одну из половин массива на каждой итерации.

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

Теперь, когда мы рассмотрели алгоритмы как линейного поиска, так и бинарного поиска, давайте сравним оба алгоритма.

Линейный поиск против бинарного поиска

Работающий

  • Линейный поиск перебирает все элементы и сравнивает их с ключом, который необходимо найти.
  • Двоичный поиск разумно уменьшает размер массива, в котором нужно искать, и каждый раз сравнивает ключ со средним элементом.

Структура данных

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

Предпосылки

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

Вариант использования

  • Линейный поиск обычно предпочтительнее для небольших и случайно упорядоченных наборов данных.
  • Двоичный поиск предпочтительнее для сравнительно больших и отсортированных наборов данных.

Эффективность

  • Линейный поиск менее эффективен в случае больших наборов данных.
  • Двоичный поиск более эффективен в случае больших наборов данных.

Сложность времени

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

Прогон, репетиция

Предположим, что у нас есть массив размером 10 000.

  • При линейном поиске сложность в лучшем случае составляет O(1), а сложность в худшем случае — O(10000).
  • В бинарном поиске сложность в лучшем случае равна O(1), а в худшем случае сложность O( log 2 10000)=O(13,287).

Заключение

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

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

Если вам интересно узнать о науке о данных, ознакомьтесь с дипломом IIIT-B & upGrad PG в области науки о данных, который создан для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические семинары, наставничество с отраслевыми экспертами, 1- on-1 с отраслевыми наставниками, более 400 часов обучения и помощи в трудоустройстве в ведущих фирмах.

Изучайте онлайн- курсы по науке о данных в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Сравните линейный поиск и бинарный поиск, используя их сложности.

Двоичный поиск во многих отношениях более оптимизирован и эффективен, чем линейный поиск, особенно когда элементы отсортированы. Причина сводится к сложности обоих поисков.
Линейный поиск
1. Временная сложность: O(N) — поскольку при линейном поиске мы просматриваем массив, чтобы проверить, соответствует ли какой-либо элемент ключу. В худшем случае элемент будет находиться в конце массива, поэтому нам придется пройти через конец, и, следовательно, временная сложность будет O(N), где N — общее количество элементов массива.
2. Пространственная сложность: O(1). Мы не используем дополнительное пространство, поэтому объемная сложность будет O(1).
Бинарный поиск
1. Временная сложность: O (log N) — в двоичном поиске поиск сокращается вдвое, так как нам нужно искать только до середины массива. И мы постоянно сокращаем наш поиск до середины раздела, где присутствует элемент.
2. Космическая сложность: O(1)
- Мы не используем дополнительное пространство, поэтому сложность пространства будет O (1).

Есть ли другой способ поиска элемента в массиве?

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

Каковы различные временные сложности интерполяционного поиска?

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