Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Поиск в массиве по порядку
Sequentially looking in an array
В информатике линейный поиск или последовательный поиск — это метод поиска элемента в списке. Он последовательно проверяет каждый элемент списка, пока не будет найдено совпадение или не будет просмотрен весь список. В худшем случае линейный поиск выполняется за линейное время и требует не более n сравнений, где n — длина списка. Если вероятность поиска каждого элемента одинакова, то в среднем линейный поиск требует сравнений, однако среднее число сравнений может изменяться, если вероятности поиска для разных элементов различаются. Линейный поиск редко бывает практичным, поскольку другие алгоритмы и структуры данных, такие как алгоритм бинарного поиска и хеш-таблицы, обеспечивают значительно более быструю скорость поиска для списков, за исключением очень коротких.
In computer science, linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in linear time in the worst case, and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.
Алгоритм
Линейный поиск последовательно проверяет каждый элемент списка, пока не обнаружит элемент, соответствующий искомому значению. Если алгоритм достигает конца списка, поиск завершается неудачно.
A linear search sequentially checks each element of the list until it finds an element that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully.
Применение
Линейный поиск обычно очень прост в реализации и практичен, когда список содержит лишь несколько элементов или выполняется единичный поиск в неупорядоченном списке. Если в одном списке необходимо найти много значений, часто целесообразно предварительно обработать список, чтобы использовать более быстрый метод. Например, можно отсортировать список и применить двоичный поиск или создать на его основе эффективную структуру данных для поиска. Если содержимое списка часто изменяется, повторная переорганизация может оказаться более затратной, чем выгодной. В результате, даже если в теории другие алгоритмы поиска могут быть быстрее линейного (например, двоичный поиск), на практике даже для массивов среднего размера (примерно до 100 элементов) использование других методов может быть нецелесообразным. Для больших массивов имеет смысл применять более быстрые методы поиска только в том случае, если объем данных достаточно велик, поскольку время, необходимое для предварительной подготовки (сортировки) данных, сопоставимо со временем, затрачиваемым на множество линейных поисков.
Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an un ordered list. When many values have to be searched in the same list, it often pays to pre process the list in order to use a faster method. For example, one may sort the list and use binary search, or build an efficient search data structure from it. Should the content of the list change frequently, repeated re organization may be more trouble than it is worth. As a result, even though in theory other search algorithms may be faster than linear search (for instance binary search), in practice even on medium sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches.