Объяснение алгоритмов линейного и двоичного поиска

Объяснение алгоритмов линейного и двоичного поиска

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





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



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





Алгоритмы линейного поиска

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

Алгоритм проверяет значение по значению, пока не найдет искомое значение или пока не закончатся значения для поиска. Когда в нем заканчиваются значения для поиска, это означает, что вашего поискового запроса нет в списке.



Алгоритм последовательного поиска принимает в качестве параметров список значений и желаемый элемент в списке. Возвращаемый результат инициализируется как Ложь и изменится на Правда когда желаемое значение найдено.

См. В качестве примера реализацию Python ниже:



def linearSearch(mylist, item):
found = False
index = 0
while index if mylist[index] == item:
found = True
else:
index = index+1
return found

Анализ алгоритмов

В лучшем случае это происходит, когда желаемый элемент стоит первым в списке. Худший случай возникает, когда желаемый элемент является последним в списке (n-й элемент). Следовательно, временная сложность линейного поиска составляет O (n).

Сценарий среднего случая в приведенном выше алгоритме - n / 2.



Связанный: Что такое нотация Big-O?

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

покупать оптом и продавать индивидуально

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

Рассмотрим пример поиска 19 в данном списке: [2, 5, 6, 11, 15, 18, 23, 27, 34]. По достижении 23 станет ясно, что искомого предмета нет в списке. Следовательно, больше не будет важно продолжать поиск по остальным элементам списка.

Алгоритмы двоичного поиска

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

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

Если меньше, то нижнюю половину списка проверять не нужно. В противном случае, если он больше, то он переходит в верхнюю половину списка.

По теме: что такое рекурсия и как ее использовать?

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

как проверить состояние батареи iphone

Этот процесс повторяется до тех пор, пока не будет найдено значение, если оно есть.

Приведенная ниже реализация Python предназначена для алгоритма двоичного поиска.

def binarySearch (mylist, элемент):

low = 0
high = len(mylist) - 1
found = False
while low <= high and not found: mid = (low + high) // 2
if mylist[mid] == item:found = True
elif item else:low = mid + 1
return found

Анализ алгоритмов

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

После первого сравнения останется n / 2 элемента. После второго останется n / 4 элемента. После третьего, n / 8.

Обратите внимание, что количество элементов продолжает уменьшаться вдвое, пока не достигнет n / 2i, где i - количество сравнений. После всего разделения у нас остается только 1 элемент.

Из этого следует:

n / 2i = 1 Следовательно, двоичный поиск - O (log n).

Переходя к сортировке

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

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

Делиться Делиться Твитнуть Эл. адрес Как использовать сортировку по выделению

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

Читать далее Похожие темы
  • Программирование
  • Объяснение технологии
  • Программирование
  • Алгоритмы
  • Анализ данных
Об авторе Джером Дэвидсон(Опубликовано 22 статей)

Джером - штатный писатель в MakeUseOf. Он освещает статьи по программированию и Linux. Он также криптоэнтузиаст и всегда следит за криптоиндустрией.

Ещё от Jerome Davidson

Подписывайтесь на нашу новостную рассылку

Подпишитесь на нашу рассылку технических советов, обзоров, бесплатных электронных книг и эксклюзивных предложений!

Нажмите здесь, чтобы подписаться