Объяснение алгоритмов линейного и двоичного поиска
Возможность поиска некоторых данных – важный аспект информатики. Алгоритмы поиска используются для поиска определенного элемента в наборе данных.
Алгоритмы возвращают логический результат (истина или ложь) поисковому запросу. Их также можно изменить, чтобы указать относительное положение найденного значения.
В этой статье алгоритмы сконцентрируются на определении того, существует ли значение.
Алгоритмы линейного поиска
Линейный поиск также известен как последовательный поиск. В этом типе поиска каждое значение в списке просматривается одно за другим в упорядоченном порядке, при этом проверяется, существует ли желаемое значение.
Алгоритм проверяет значение по значению, пока не найдет искомое значение или пока не закончатся значения для поиска. Когда в нем заканчиваются значения для поиска, это означает, что вашего поискового запроса нет в списке.
Алгоритм последовательного поиска принимает в качестве параметров список значений и желаемый элемент в списке. Возвращаемый результат инициализируется как False и изменится на True, когда желаемое значение будет найдено.
См. В качестве примера реализацию Python ниже:
def linearSearch (mylist, элемент):
found = False
индекс = 0
в то время как index <len (mylist) и не найден:
если mylist [index] == item:
found = True
еще:
индекс = индекс + 1
возврат найден
Анализ алгоритмов
В лучшем случае это происходит, когда желаемый элемент стоит первым в списке. Худший случай возникает, когда желаемый элемент является последним в списке (n-й элемент). Следовательно, временная сложность линейного поиска составляет O (n).
Сценарий среднего случая в приведенном выше алгоритме – n / 2.
Модифицированный линейный поиск
Важно знать, что используемый алгоритм предполагает, что ему предоставляется случайный список элементов. То есть элементы списка не расположены в определенном порядке.
Предположим, что элементы расположены в определенном порядке, скажем, от наименьшего к наибольшему. Можно было бы добиться некоторого преимущества в вычислениях.
Возьмем, к примеру, поиск 19 в данном списке: [2, 5, 6, 11, 15, 18, 23, 27, 34]. По достижении 23 станет ясно, что искомого предмета нет в списке. Следовательно, больше не будет важно продолжать поиск по остальным элементам списка.
Алгоритмы двоичного поиска
Вы видели, как упорядоченный список может сократить необходимые вычисления. Алгоритм двоичного поиска пользуется еще большей эффективностью, чем упорядоченный список.
Алгоритм начинается с того, что берется среднее значение упорядоченного списка и проверяется, является ли оно желаемым. Если это не так, то значение проверяется, меньше оно или больше желаемого значения.
Если меньше, то нижнюю половину списка проверять не нужно. В противном случае, если он больше, то он переходит в верхнюю половину списка.
Независимо от того, какой подсписок (левый или правый) выбран, среднее значение будет снова определено. Значение снова проверяется, если это требуемое значение. Если нет, проверяется, больше или меньше запрошенного значения.
Этот процесс повторяется до тех пор, пока не будет найдено значение, если оно есть.
Приведенная ниже реализация Python предназначена для алгоритма двоичного поиска.
def binarySearch (мой список, элемент):
низкий = 0
high = len (mylist) – 1
found = False
пока низкий <= высокий и не найден:
mid = (низкий + высокий) // 2
если mylist [mid] == item:
found = True
elif item <mylist [mid]:
высокий = средний – 1
еще:
низкий = средний + 1
возврат найден
Анализ алгоритмов
В лучшем случае возникает ситуация, когда желаемый элемент оказывается средним. Однако худший сценарий не так прост. Следуйте приведенному ниже анализу:
После первого сравнения останется n / 2 элемента. После второго останется n / 4 элемента. После третьего, n / 8.
Обратите внимание, что количество элементов продолжает уменьшаться вдвое, пока не достигнет n / 2i, где i – количество сравнений. После всего разделения у нас остается только 1 элемент.
Из этого следует:
п / 2i = 1
Следовательно, двоичный поиск – это O (log n).
Переходя к сортировке
В бинарном поиске мы рассматривали случай, когда данный массив уже упорядочен. Но предположим, что у вас есть неупорядоченный набор данных, и вы хотите выполнить бинарный поиск по нему. Что бы вы сделали?
Ответ прост: рассортируйте. В информатике существует ряд хорошо изученных методов сортировки. Один из этих методов, который вы можете начать изучать, – это алгоритм сортировки по выбору, у нас есть множество руководств, относящихся и к другим областям.