В чем разница между линейным поиском и двоичным поиском?
В чем разница между линейным поиском и двоичным поиском?
Ответ 1
A линейный поиск смотрит вниз по списку, по одному пункту за раз, без прыжка. С точки зрения сложности это поиск O(n) - время, затрачиваемое на поиск списка, увеличивается с той же скоростью, что и список.
A бинарный поиск - это когда вы начинаете с середины отсортированного списка и видите, больше или меньше значения, re look for, который определяет, находится ли значение в первой или второй половине списка. Переходим на полпути через подсписку и сравниваем снова и т.д. Это в значительной степени зависит от того, как люди обычно ищут слово в словаре (хотя мы используем лучшие эвристики, очевидно - если вы ищете "кошку", вы не начинать с "М" ). С точки зрения сложности это поиск O(log n) - количество поисковых операций растет медленнее, чем список, потому что вы сокращаете вдвое "пространство поиска" с каждой операцией.
В качестве примера предположим, что вы искали U в списке букв A-Z (индекс 0-25, мы ищем значение в индексе 20).
Линейный поиск спросит:
list[0] == 'U'? Нет.
list[1] == 'U'? Нет.
list[2] == 'U'? Нет.
list[3] == 'U'? Нет.
list[4] == 'U'? Нет.
list[5] == 'U'? Нет.
...list[20] == 'U'? Да. Закончено.
В двоичном поиске будет задаваться вопрос:
Сравните
list[12]('M') с 'U': Меньше, смотрите дальше. (Диапазон = 13-25)
Сравнитеlist[19]('T') с 'U': Меньше, смотрите дальше. (Диапазон = 20-25)
Сравнитеlist[22]('W') с 'U': Больше, смотрите раньше. (Диапазон = 20-21)
Сравнитеlist[20]('U') с 'U': Найди его! Закончено.
Сравнение двух:
- Для двоичного поиска требуются сортировка входных данных; линейный поиск не
- Для двоичного поиска требуется сравнение заказов; линейный поиск требует только сравнений сравнений.
- Двоичный поиск имеет сложность O (log n); линейный поиск имеет сложность O (n), как обсуждалось ранее
- Для двоичного поиска требуется произвольный доступ к данным; линейный поиск требует только последовательного доступа (это может быть очень важно - это означает, что линейный поиск может передавать данные произвольного размера)
Ответ 2
Подумайте об этом как о двух разных способах найти свой путь в телефонной книге. Линейный поиск начинается с самого начала, читая каждое имя, пока вы не найдете то, что ищете. С другой стороны, двоичный поиск - это когда вы открываете книгу (обычно посередине), смотрите имя вверху страницы и решаете, больше или меньше имя, которое вы ищете, чем тот, который вы "Ищем. Если имя, которое вы ищете, больше, вы продолжаете искать верхнюю часть книги именно таким образом.
Ответ 3
Я хотел бы добавить одну разницу -
Для значений линейного поиска не нужно сортировать.
Но для двоичного поиска значения должны быть отсортированы в порядке.
Ответ 4
Линейный поиск работает, просматривая каждый элемент в списке данных, пока он не найдет цель или не достигнет конца. Это приводит к производительности O (n) в данном списке. Бинарный поиск поставляется с необходимым условием для сортировки данных. Мы можем использовать эту информацию, чтобы уменьшить количество элементов, которые нам нужны, чтобы найти нашу цель. Мы знаем, что если мы посмотрим на случайный элемент в данных (пусть, средний элемент), и этот элемент больше нашей цели, то все элементы справа от этого элемента также будут больше, чем наша цель. Это означает, что нам нужно только посмотреть на левую часть данных. В принципе, каждый раз, когда мы ищем цель и пропустите, мы можем устранить половину оставшихся предметов. Это дает нам хорошую сложность времени O (log n).
Просто помните, что данные сортировки, даже с самым эффективным алгоритмом, всегда будут медленнее линейного поиска (самыми быстрыми алгоритмами сортировки являются O (n * log n)). Поэтому вы никогда не должны сортировать данные только для выполнения одного бинарного поиска позже. Но если вы будете выполнять множество поисковых запросов (скажем, как минимум, O (log n)), может быть целесообразно отсортировать данные, чтобы вы могли выполнять бинарные поиски. В таких ситуациях вы можете также рассмотреть другие структуры данных, такие как хеш-таблица.
Ответ 5
Линейный поиск начинается с начала списка значений и проверяет 1 на 1 для получения результата, который вы ищете.
Двоичный поиск начинается в середине отсортированного массива и определяет, какая сторона (если есть), значение, которое вы ищете, включено. То, что "половина" массива затем обыскивается снова таким же образом, каждый раз разделяя результаты пополам на два.
Ответ 6
Обязательно подумайте о том, стоит ли выигрывать быстрый бинарный поиск стоимости сортировки списка (чтобы иметь возможность использовать двоичный поиск). То есть если у вас много операций вставки/удаления и только случайный поиск, бинарный поиск может в общем случае быть медленнее, чем линейный поиск.
Ответ 7
Попробуйте следующее: выберите случайное имя "Фамилия, имя и фамилия" и найдите его в своей телефонной книге.
1-й раз: начинайте с начала книги, читая имена, пока не найдете их, или найдите место, где оно произошло бы в алфавитном порядке, и обратите внимание, что его нет.
2-й раз: откройте книгу на половине пути и посмотрите на страницу. Спросите себя, должен ли этот человек находиться слева или справа. Какой бы он ни был, возьмите это 1/2 и найдите его середину. Повторяйте эту процедуру до тех пор, пока не найдете страницу, где должна быть запись, а затем либо применить тот же процесс к столбцам, либо просто искать линейно вдоль имен на странице, как и раньше.
Время для обоих методов и отчёт!
[также подумайте, какой подход лучше, если все, что у вас есть, это список имен, не отсортированный...]
Ответ 8
Линейный поиск, также называемый последовательным поиском, смотрит на каждый элемент в последовательности с самого начала, чтобы увидеть, присутствует ли требуемый элемент в структуре данных. Когда количество данных невелико, этот поиск выполняется быстро. Он простой, но необходимый для работы пропорционален количеству данных для поиска. Удвоение количества элементов удваивает время поиска, если нужный элемент отсутствует.
Двоичный поиск эффективен для большего массива. В этом мы проверяем средний элемент. Если значение больше того, что мы ищем, тогда посмотрите в первом тайме, иначе посмотрите во второй половине. Повторяйте это до тех пор, пока не будет найден нужный элемент. Таблица должна быть отсортирована для двоичного поиска. Он исключает половину данных на каждой итерации. Он логарифмичен.
Если у нас есть 1000 элементов для поиска, бинарный поиск занимает около 10 шагов, линейный поиск 1000 шагов.
Ответ 9
бинарный поиск выполняется в O (logn), тогда как линейный поиск выполняется в O (n) раз, поэтому бинарный поиск имеет лучшую производительность
Ответ 10
Линейный поиск смотрит вниз по списку, по одному пункту за раз, без прыжка. С точки зрения сложности это поиск O (n) - время, затрачиваемое на поиск списка, увеличивается с той же скоростью, что и список.
Двоичный поиск - это когда вы начинаете с середины отсортированного списка и видите, больше или меньше значения, которое вы ищете, которое определяет, находится ли значение в первой или второй половине списка, Переходим на полпути через подсписку и сравниваем снова и т.д. Это в значительной степени зависит от того, как люди обычно ищут слово в словаре (хотя мы используем лучшие эвристики, очевидно - если вы ищете "кошку", вы не начинать с "М" ). С точки зрения сложности это поиск O (log n) - количество операций поиска растет медленнее, чем список, потому что вы сокращаете вдвое "пространство поиска" с каждой операцией.
Ответ 11
Linear Search просматривает элементы, пока не найдет искомое значение.
Эффективность: O(n)
Пример кода Python:
test_list = [1, 3, 9, 11, 15, 19, 29]
test_val1 = 25
test_val2 = 15
def linear_search(input_array, search_value):
index = 0
while (index < len(input_array)) and (input_array[index] < search_value):
index += 1
if index >= len(input_array) or input_array[index] != search_value:
return -1
return index
print linear_search(test_list, test_val1)
print linear_search(test_list, test_val2)
Binary Search находит средний элемент массива. Проверяет, что среднее значение больше или меньше значения поиска. Если он меньше, он получает левую часть массива и находит средний элемент этой части. Если он больше, получает нужную часть массива. Он выполняет операцию до тех пор, пока не найдет искомое значение. Или, если в массиве нет значения, заканчивается поиск.
Эффективность: O(logn)
Пример кода Python:
test_list = [1, 3, 9, 11, 15, 19, 29]
test_val1 = 25
test_val2 = 15
def binary_search(input_array, value):
low = 0
high = len(input_array) - 1
while low <= high:
mid = (low + high) / 2
if input_array[mid] == value:
return mid
elif input_array[mid] < value:
low = mid + 1
else:
high = mid - 1
return -1
print binary_search(test_list, test_val1)
print binary_search(test_list, test_val2)
Также вы можете увидеть визуализированную информацию о линейном и двоичном поиске здесь: https://www.cs.usfca.edu/~galles/visualization/Search.html
Ответ 12
Для ясного понимания, пожалуйста, взгляните на мои реализации codepen https://codepen.io/serdarsenay/pen/XELWqN
Самым большим отличием является необходимость сортировки вашей выборки перед применением бинарного поиска, поэтому для большинства выборок "нормального размера" (то есть, для спора) поиск будет быстрее с использованием алгоритма линейного поиска.
Вот код javascript, для html и css, а также полный пример, пожалуйста, обратитесь к ссылке выше codepen.
var unsortedhaystack = [];
var haystack = [];
function init() {
unsortedhaystack = document.getElementById("haystack").value.split(' ');
}
function sortHaystack() {
var t = timer('sort benchmark');
haystack = unsortedhaystack.sort();
t.stop();
}
var timer = function(name) {
var start = new Date();
return {
stop: function() {
var end = new Date();
var time = end.getTime() - start.getTime();
console.log('Timer:', name, 'finished in', time, 'ms');
}
}
};
function lineerSearch() {
init();
var t = timer('lineerSearch benchmark');
var input = this.event.target.value;
for(var i = 0;i<unsortedhaystack.length - 1;i++) {
if (unsortedhaystack[i] === input) {
document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
console.log(document.getElementById('result').innerHTML);
t.stop();
return unsortedhaystack[i];
}
}
}
function binarySearch () {
init();
sortHaystack();
var t = timer('binarySearch benchmark');
var firstIndex = 0;
var lastIndex = haystack.length-1;
var input = this.event.target.value;
//currently point in the half of the array
var currentIndex = (haystack.length-1)/2 | 0;
var iterations = 0;
while (firstIndex <= lastIndex) {
currentIndex = (firstIndex + lastIndex)/2 | 0;
iterations++;
if (haystack[currentIndex] < input) {
firstIndex = currentIndex + 1;
//console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
} else if (haystack[currentIndex] > input) {
lastIndex = currentIndex - 1;
//console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
} else {
document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
console.log(document.getElementById('result').innerHTML);
t.stop();
return true;
}
}
}