В чем разница между линейным и двоичным поиском?

Question

В чем разница между линейным поиском и бинарным поиском?

Answer 1

A линейный поиск просматривает список, по одному элементу за раз, без прыжков. С точки зрения сложности это поиск O(n) - время, которое требуется для поиска в списке, увеличивается с той же скоростью, что и список.

A бинарный поиск - это когда вы начинаете с середины отсортированного списка и видите, больше или меньше искомого значения, которое определяет, находится ли значение в первом или вторая половина списка. Перейдите на половину списка подсписков, сравните еще раз и т. Д. Это в значительной степени то, как люди обычно ищут слово в словаре (хотя мы, конечно, используем лучшую эвристику - если вы ищете "кошку", вы этого не делаете начать с "М"). С точки зрения сложности это 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), как обсуждалось ранее
• Бинарный поиск требует произвольного доступа к данным; Для линейного поиска требуется только последовательный доступ (это может быть очень важно - это означает, что линейный поиск может поток данных произвольного размера)

Answer 2

Думайте об этом как о двух разных способах поиска вашего пути в телефонной книге. Линейный поиск начинается с начала, читая каждое имя, пока вы не найдете то, что ищете. С другой стороны, бинарный поиск - это когда вы открываете книгу (обычно посередине), смотрите на имя вверху страницы и решаете, является ли искомое имя больше или меньше того, которое вы ищу. Если имя, которое вы ищете, больше, то вы продолжаете искать верхнюю часть книги именно таким образом.

Answer 3

Линейный поиск работает, просматривая каждый элемент в списке данных, пока он не найдет цель или не достигнет конца. Это приводит к производительности O (n) в данном списке. Бинарный поиск поставляется с условием, что данные должны быть отсортированы. Мы можем использовать эту информацию, чтобы уменьшить количество элементов, на которые мы должны обратить внимание, чтобы найти нашу цель. Мы знаем, что если мы посмотрим на случайный элемент в данных (скажем, на средний элемент), и этот элемент будет больше нашей цели, то все элементы справа от этого элемента также будут больше нашей цели. Это означает, что нам нужно взглянуть только на левую часть данных. По сути, каждый раз, когда мы ищем цель и промахиваемся, мы можем устранить половину оставшихся предметов. Это дает нам хорошую O (log n) временную сложность.

Просто помните, что сортировка данных, даже с самым эффективным алгоритмом, всегда будет медленнее, чем линейный поиск (самые быстрые алгоритмы сортировки - O (n * log n)). Таким образом, вы никогда не должны сортировать данные только для того, чтобы потом выполнить один двоичный поиск. Но если вы будете выполнять много поисков (скажем, по крайней мере O (log n) поисков), возможно, стоит отсортировать данные, чтобы вы могли выполнять двоичные поиски. Вы можете также рассмотреть другие структуры данных, такие как хеш-таблица в таких ситуациях.

Answer 4

Обязательно обсудите, стоит ли выигрыш от более быстрого бинарного поиска затрат на поддержание сортировки списка (чтобы иметь возможность использовать бинарный поиск). То есть если у вас много операций вставки / удаления и только случайный поиск, бинарный поиск может быть медленнее, чем линейный поиск.

Answer 5

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

Бинарный поиск начинается в середине отсортированного массива и определяет, на какой стороне (если есть) находится значение, которое вы ищете. Затем эту «половину» массива снова ищут таким же образом, каждый раз разделяя результаты пополам на два.

Answer 6

Попробуйте: выберите случайное имя «Фамилия, Имя» и найдите его в своей телефонной книге.

1-й раз: начните с начала книги, читая имена, пока не найдете ее, или найдите место, где это произошло бы в алфавитном порядке, и обратите внимание, что его там нет.

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

Время обоих методов и отчет!

[также подумайте, какой подход лучше, если у вас есть только список имен, а не отсортированный ...]

Answer 7

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

Бинарный поиск - это когда вы начинаете с середины отсортированного списка и видите, больше или меньше искомого значения, что определяет, находится ли значение в первой или второй половине списка , Перейдите на половину списка подсписков, сравните еще раз и т. Д. Это в значительной степени то, как люди обычно ищут слово в словаре (хотя мы, конечно, используем лучшую эвристику - если вы ищете "кошку", вы этого не делаете начать с "М"). В терминах сложности это поиск O (log n) - число поисковых операций растет медленнее, чем в списке, потому что вы уменьшаете пополам «пространство поиска» с каждой операцией.

Answer 8

двоичный поиск выполняется за время O (logn), тогда как линейный поиск выполняется за O (n) раз, поэтому бинарный поиск имеет лучшую производительность

Answer 9

Линейный поиск, также называемый последовательным поиском, просматривает каждый элемент в последовательности с самого начала, чтобы увидеть, присутствует ли нужный элемент в структуре данных. Когда объем данных невелик, этот поиск выполняется быстро. Это просто, но необходимая работа пропорциональна количеству данных, которые необходимо найти. Удвоение количества элементов удвоит время поиска, если требуемый элемент отсутствует.

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

Если у нас есть 1000 элементов для поиска, бинарный поиск занимает около 10 шагов, линейный поиск - 1000 шагов.

Answer 10

Для ясного понимания, пожалуйста, взгляните на мои реализации 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;
    }
  }
}