Вступление
В этой статье мы собираемся обсудить два наиболее часто используемых алгоритма поиска в мире программирования.
- Линейный поиск
- Бинарный поиск
Алгоритм поиска пути из точки А в точку Б на C# — одна из самых распространенных задач при разработке игр. Для решения этой задачи есть множество алгоритмов, но самым часто используемым является A* (A star).
Мы будем объяснять алгоритмы с помощью примера.
Линейный поиск
Этот алгоритм будет выполнять последовательный поиск элемента в заданном массиве. Каждый элемент проверяется от начала до конца, и если совпадение найдено, будет возвращен индекс соответствующего элемента; в противном случае -1 будет возвращено.
Псевдокод для линейного поиска
procedure LinearSearch(array, value)
foreach item in array
if item == value
return the item's index
end if
end foreach
return -1
end procedure
Позвольте нам понять это с помощью примера.
Рассмотрим массив ниже.
Если мы хотим определить позицию числа 1 в этом массиве, мы должны пройти каждый элемент от начала до конца; т.е. от index = 0 до index = 7 и сравним его с 1. Мы вернем позицию элемента, которая соответствует 1, что равно 6 (index + 1). Следовательно, элемент 1 находится в позиции 6 во входном массиве.
Сложность во времени
Поскольку все элементы массива сравниваются только один раз с входным элементом, следовательно, временная сложность линейного поиска составляет O (N).
Бинарный поиск
Бинарный поиск – это эффективный и часто используемый алгоритм поиска. Этот алгоритм работает только с отсортированными наборами элементов. Поэтому, если данный массив не отсортирован, нам нужно отсортировать его перед применением бинарного поиска.
Этот алгоритм ищет отсортированный массив путем многократного деления интервала поиска пополам. Начните с интервала, охватывающего весь массив. Если значение ключа поиска меньше, чем элемент в середине интервала, сузьте интервал до нижней половины. В противном случае сузьте его до верхней половины. Повторно проверяйте до тех пор, пока значение не будет найдено или интервал не будет пустым. Если найденное значение возвращает индекс соответствующего элемента, иначе возвращается -1.
Псевдокод для бинарного поиска
Procedure BinarySearch(array,value)
Set lowBound = 1
Set uppBound = size of array
while (lowBound <= uppBound)
set midPoint = (lowBound + uppBound ) / 2
if array[midPoint] > value
set uppBound = midPoint - 1
else if array[midPoint] < value
set lowBound = midPoint + 1
else return midPoint
end while
return -1;
end procedure
Позвольте нам понять это с помощью примера.
Ссылаясь на изображение ниже; если нам нужно найти позицию 2 в данном массиве, используя бинарный поиск,
Нижняя граница равна 0, а верхняя граница равна 7. Медиана нижней и верхней границ равна (lower_bound + upper_bound) / 2 = 3. Здесь массив [3] = 4. Значение среднего элемента (4) больше значения значение, которое будет найдено (2). Следовательно, нам не нужно проводить поиск по любому элементу, кроме 4, поскольку элементы за ним, очевидно, будут больше, чем 2.
Поэтому мы опускаем верхнюю границу массива в положение элемента непосредственно перед средним элементом. Теперь мы следуем той же процедуре в том же массиве со следующими значениями,
Теперь нижняя граница равна 0, а верхняя граница равна 2. Медиана нижней и верхней границ равна (lower_bound + upper_bound) / 2 = 1. Здесь array [1] = 2. Поэтому значение среднего элемента соответствует значению поэтому мы возвращаем позицию 2 как 2.
Сложность во времени
Массив для поиска уменьшается наполовину в каждой итерации. Следовательно, временная сложность двоичного поиска составляет O (LogN).
Линейный поиск и бинарный поиск
Линейный поиск – это последовательный поиск, который сканирует по одному элементу за раз. Время, затрачиваемое на поиск данного элемента, увеличивается, если количество элементов в массиве увеличивается.
Для двоичного поиска входной массив должен быть в отсортированном порядке. Он также обращается к данным случайным образом, так как он всегда сравнивается со средним элементом массива и, следовательно, отбрасывает половину массива в каждой итерации.
Линейный поиск выполняет сравнение на равенство, тогда как бинарный поиск выполняет сравнение на основе порядка
Заключение
В этой статье мы узнали о линейном поиске и бинарном поиске. Об этом могут спросить на собеседованиях.