В этом посте я буду сравнивать алгоритмы линейного поиска и двоичного поиска. Вы увидите псевдокод для каждого алгоритма, а также примеры и пошаговое руководство по его реализации.
Вступление
Как программист, вы хотите найти лучшее решение проблемы, чтобы ваш код был не только правильным, но и эффективным. Выбор неоптимального алгоритма может означать более длительное время завершения, повышенную сложность кода или, что хуже, программу, которая аварийно завершает работу.
Возможно, вы использовали алгоритм поиска, чтобы найти элементы в коллекции данных. Язык JavaScript имеет несколько методов, таких как find , для поиска элементов в массиве. Однако эти методы используют линейный поиск. Алгоритм линейного поиска начинается в начале списка и сравнивает каждый элемент со значением поиска, пока он не будет найден.
Это хорошо, когда у вас есть небольшое количество элементов. Но когда вы ищете большие списки, которые содержат тысячи или миллионы элементов, вам нужен лучший способ найти элементы. Это когда вы будете использовать бинарный поиск.
В этом уроке я объясню, как работает бинарный поиск и как реализовать алгоритм в JavaScript. Сначала рассмотрим алгоритм линейного поиска.
Линейный поиск
Мы начнем с объяснения того, как реализовать линейный поиск в JavaScript. Мы создадим функцию с именем linearSearch которая принимает значение, являющееся целым числом или строкой, и массив в качестве параметров. Функция будет искать значение в каждом элементе массива и возвращать позицию значения в массиве, если оно найдено. Если значение отсутствует в массиве, оно вернет -1. Например, вызов linearSearch(1, [3, 4, 2, 1, 5]) вернет 3, а вызов linearSearch(0, [3, 4, 2, 1, 5]) вернет -1.
Вот некоторый псевдокод для нашей функции:
|
1
2
3
4
5
6
7
8
9
|
Set found to false
Set position to −1
Set index to 0
while found is false and index < number of elements
if list[index] is equal to search value
Set found to true
Set position to index
else Add 1 to index
return position
|
Реализация линейного поиска в JavaScript
Вот JavaScript-реализация алгоритма линейного поиска:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
function linearSearch(value, list) {
let found = false;
let position = -1;
let index = 0;
while(!found && index < list.length) {
if(list[index] == value) {
found = true;
position = index;
} else {
index += 1;
}
}
return position;
}
|
Важно отметить, что алгоритм линейного поиска не должен использовать отсортированный список. Также алгоритм может быть настроен для использования в различных сценариях, таких как поиск массива объектов по ключу. Если у вас есть массив данных о клиентах, который включает ключи для имени и фамилии, вы можете проверить, есть ли в массиве клиент с указанным именем. В этом случае вместо проверки того, равен ли list[index] нашему поисковому значению, вы должны проверить list[index].first .
В приведенном выше примере я использовал функцию linearSearch для массива из пяти элементов. В худшем случае, когда искомое значение отсутствует в списке или находится в конце списка, функция должна будет выполнить пять сравнений. Поскольку наш массив очень мал, нет необходимости оптимизировать его, используя другой алгоритм. Однако после определенного момента использование алгоритма линейного поиска более неэффективно, и тогда лучше использовать алгоритм двоичного поиска.
Бинарный поиск
Представьте, что вы играете в угадайку чисел. Вас попросят угадать число от 1 до 100. Если ваш номер слишком высокий или слишком низкий, вы получите подсказку.
Какой будет ваша стратегия? Вы бы выбрали номера случайно? Начнете ли вы с 1, затем с 2 и так далее, пока не догадаетесь правильно? Даже если у вас было неограниченное количество догадок, вы хотите сделать правильное предположение за минимальное количество попыток. Следовательно, вы можете начать с угадывания 50. Если число выше, вы можете угадать 75. Если оно меньше, то это означает, что число находится в диапазоне от 50 до 75, и вы должны выбрать число, которое находится в середине. Вы будете продолжать в том же духе, пока не достигнете правильного номера. Это похоже на то, как работает бинарный поиск.
В отличие от линейного поиска, бинарный поиск использует отсортированный список. Для поиска значения вы сначала сравниваете значение со средним элементом списка. Если они равны, значение поиска найдено. Если значение поиска больше, чем средний элемент, вы ищите верхнюю половину данных. Затем вы сравниваете средний элемент этого раздела со значением поиска. В качестве альтернативы, если элемент меньше среднего элемента, вы ищите нижнюю половину списка и сравниваете его среднее значение. Список многократно делится пополам до тех пор, пока элемент не будет найден или не останется элементов для поиска.
Для поиска 9 в списке:
|
1
|
1 2 3 4 5 6 7 8 9 10
|
Сначала мы находим средний элемент. Это элемент в позиции Math.floor((first + last)/2) , где first — первый индекс, а last — последний индекс. Мы выбираем округление так, чтобы, если результат был дробью, он стал целым числом. Средний элемент в этом списке равен 5. Наше поисковое значение 9 больше 5, поэтому мы ищем список:
|
1
|
6 7 8 9 10
|
Средний элемент этой части равен 8. Девять больше, чем 8, поэтому мы ищем список:
|
1
|
9 10
|
Средний элемент равен 9, поэтому мы можем остановить наш поиск здесь.
Вот некоторый псевдокод, который выражает вышеупомянутый алгоритм для двоичного поиска:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
Set first to 0
Set last to the last index in the list
Set found to false
Set position to −1
while found is false and first is less than or equal to last
Set middle to the index halfway between first and last
if list[middle] equals the desired value
Set found to true
Set position to middle
else if list[middle] is greater than the desired value
Set last to middle − 1
else
Set first to middle + 1
return position
|
Реализация бинарного поиска в JavaScript
Теперь давайте закодируем алгоритм двоичного поиска в JavaScript!
Мы создадим функцию binarySearch , которая принимает значение и массив в качестве параметров. Он вернет индекс, где значение встречается в списке, если найдено. Если значение не найдено, возвращается -1. Это наша реализация, написанная на JavaScript:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
|
function binarySearch(value, list) {
let first = 0;
let last = list.length — 1;
let position = -1;
let found = false;
let middle;
while (found === false && first <= last) {
middle = Math.floor((first + last)/2);
if (list[middle] == value) {
found = true;
position = middle;
} else if (list[middle] > value) { //if in lower half
last = middle — 1;
} else { //in in upper half
first = middle + 1;
}
}
return position;
}
|
Вывод
В этом уроке мы увидели, как реализовать линейный поиск и алгоритм двоичного поиска. Алгоритм линейного поиска проще и не требует отсортированного массива. Тем не менее, это неэффективно для использования с большими массивами. В худшем случае алгоритм должен будет искать все элементы, делая n сравнений (где n — количество элементов).
С другой стороны, алгоритм двоичного поиска требует, чтобы вы сначала отсортировали массив, и его сложнее реализовать. Однако это более эффективно, даже если учитывать стоимость сортировки. Например, массив из 10 элементов может сделать не более 4 сравнений для бинарного поиска против 10 для линейного поиска — не такое большое улучшение. Однако для массива с 1 000 000 элементов наихудший случай в бинарном поиске — всего 20 сравнений. Это огромное улучшение по сравнению с линейным поиском!
Знание того, как использовать бинарный поиск, — это не просто вопрос практики для интервью. Это практический навык, который может сделать ваш код более эффективным.