Линейный поиск - История изменений

Patarakin в 16:55, 15 декабря 2022

2022-12-15T16:55:11Z

← Предыдущая версия		Версия от 19:55, 15 декабря 2022
Строка 81:		Строка 81:
	----		----
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]
			[[Category:Scripting Tutorials]]

Patarakin: /* Есть или нет в списке */

2022-12-14T15:21:11Z

Есть или нет в списке

← Предыдущая версия		Версия от 18:21, 14 декабря 2022
Строка 8:		Строка 8:

	=== Есть или нет в списке ===		=== Есть или нет в списке ===
	[[Файл:Linear Search+ script pic.png]]		[[Файл:Linear Search+ script pic.png\|800px]]

	=== Положение в списке ===		=== Положение в списке ===

Patarakin: /* Пример на Snap! */

2022-12-14T15:20:48Z

Пример на Snap!

← Предыдущая версия		Версия от 18:20, 14 декабря 2022
Строка 5:		Строка 5:
	В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.		В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.

	== ~~Пример~~ на [[Snap!]] ==		== Примеры на [[Snap!]] ==

			=== Есть или нет в списке ===
			[[Файл:Linear Search+ script pic.png]]

			=== Положение в списке ===
	[[Файл:Linear search.png\|600px]]		[[Файл:Linear search.png\|600px]]

Patarakin: /* Пример */

2022-12-13T17:49:10Z

Пример

← Предыдущая версия		Версия от 20:49, 13 декабря 2022
Строка 4:		Строка 4:

	В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.		В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.

			== Пример на [[Snap!]] ==

			[[Файл:Linear search.png\|600px]]

	== Пример ==		== Пример ==

Patarakin в 13:40, 1 декабря 2022

2022-12-01T13:40:37Z

← Предыдущая версия		Версия от 16:40, 1 декабря 2022
Строка 16:		Строка 16:
	return -1; // элемент не найден		return -1; // элемент не найден
	end;		end;
	</pre>Пример на Swift 3, с "ускоренным" поиском:<syntaxhighlight lang="swift" line="1">		</pre>


			=== Пример на [[Swift]] ===
			Пример на [[Swift]] 3, с "ускоренным" поиском:<syntaxhighlight lang="swift" line="1">
	func linearSearch(element: Int, in array: [Int]) -> Int? {		func linearSearch(element: Int, in array: [Int]) -> Int? {
	var array = array		var array = array
Строка 67:		Строка 71:
	Если предполагается поиск в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например, [[Алгоритм сортировки\|сортировки]] и последующего использования [[Бинарный поиск\|бинарного поиска]], либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.		Если предполагается поиск в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например, [[Алгоритм сортировки\|сортировки]] и последующего использования [[Бинарный поиск\|бинарного поиска]], либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.

			----
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]

Patarakin в 17:56, 19 октября 2022

2022-10-19T17:56:46Z

← Предыдущая версия		Версия от 20:56, 19 октября 2022
Строка 67:		Строка 67:
	Если предполагается поиск в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например, [[Алгоритм сортировки\|сортировки]] и последующего использования [[Бинарный поиск\|бинарного поиска]], либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.		Если предполагается поиск в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например, [[Алгоритм сортировки\|сортировки]] и последующего использования [[Бинарный поиск\|бинарного поиска]], либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.

	~~== См. также ==~~
	* [[Двоичный поиск]]
	* [[Метод дихотомии]]
	* [[Метод золотого сечения]]
	* [[Троичный поиск]]
	* [[Полный перебор]]

	~~== Литература ==~~
	* {{книга
	~~\|подзаголовок~~
	~~\|заглавие=Искусство программирования, том 3. Сортировка и поиск~~
	~~\|оригинал=The Art of Computer Programming, vol.3. Sorting and Searching~~
	~~\|ссылка=~~
	~~\|автор=[[Дональд Кнут ]]~~
	~~\|издание = 2-е изд~~
	~~\|год=2007~~
	~~\|место=М.~~
	~~\|издательство= [[Вильямс (издательство)\|«Вильямс»]]~~
	~~\|страницы= 824~~
	~~\|isbn= 0-201-89685-0~~
	}}
	~~{{нет сносок}}~~
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:54:56Z

1 версия импортирована

← Предыдущая версия	Версия от 20:54, 19 октября 2022
(нет различий)

ru_wikipedia>Vbif-routine в 16:55, 2 июля 2021

2021-07-02T16:55:28Z

Новая страница

'''Линейный, последовательный поиск''' — [[алгоритм]] нахождения заданного значения [[Функция (математика)|произвольной функции]] на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и, в отличие, например, от [[двоичный поиск|двоичного поиска]], не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

Если отрезок имеет длину N, то найти решение с точностью до <math>\epsilon</math> можно за время <math>N\over\epsilon</math>. Т.о. [[Сложность алгоритма|асимптотическая сложность алгоритма]] — <math>O(n)</math>. В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют, только если отрезок поиска содержит очень мало элементов, тем не менее, линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Также линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.

В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.

== Пример ==
[[переменная (программирование)|Переменные]] <math>L</math> и <math>R</math> содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. То есть в результате каждой проверки область поиска уменьшается на один элемент.

<pre>
int function LinearSearch (Array A, int L, int R, int Key);
begin
for X = L to R do
if A[X] = Key then
return X
return -1; // элемент не найден
end;
</pre>Пример на Swift 3, с "ускоренным" поиском:<syntaxhighlight lang="swift" line="1">
func linearSearch(element: Int, in array: [Int]) -> Int? {
var array = array

let realLastElement: Int?
if array.isEmpty {
return nil
} else {
realLastElement = array[array.count - 1]
array[array.count - 1] = element
}

var i = 0;
while array[i] != element {
i += 1;
}

let findedElement = array[i];
if i == array.count - 1 && findedElement != realLastElement {
return nil
} else {
return i
}
}
</syntaxhighlight>

== Анализ ==
Для списка из ''n'' элементов лучшим случаем будет тот, при котором искомое значение равно первому элементу списка и требуется только одно сравнение. Худший случай будет тогда, когда значения в списке нет (или оно находится в самом конце списка), в случае чего необходимо ''n'' сравнений.

Если искомое значение входит в список ''k'' раз и все вхождения равновероятны, то ожидаемое число сравнений

: <math>
\begin{cases}
n & k = 0 \\[5pt]
\displaystyle\frac{n + 1}{k + 1} & 1 \le k \le n.
\end{cases}
</math>

Например, если искомое значение встречается в списке один раз, и все вхождения равновероятны, то среднее число сравнений равно <math>\frac{n + 1}2</math>.
Однако, если ''известно'', что оно встречается один раз, то достаточно ''n'' — 1 сравнений, и среднее число сравнений будет равняться
: <math>\displaystyle\frac{(n + 2)(n-1)}{2n}</math>

(для ''n'' = 2 это число равняется 1, что соответствует одной конструкции if-then-else).

В любом случае [[вычислительная сложность]] алгоритма [[«O» большое и «o» малое|O]](''n'').

== Приложения ==
Обычно линейный поиск очень прост в реализации и применим, если список содержит мало элементов, либо в случае одиночного поиска в неупорядоченном списке.

Если предполагается поиск в одном и том же списке большое число раз, то часто имеет смысл предварительной обработки списка, например, [[Алгоритм сортировки|сортировки]] и последующего использования [[Бинарный поиск|бинарного поиска]], либо построения какой-либо эффективной структуры данных для поиска. Частая модификация списка также может оказывать влияние на выбор дальнейших действий, поскольку делает необходимым процесс перестройки структуры.

== См. также ==
* [[Двоичный поиск]]
* [[Метод дихотомии]]
* [[Метод золотого сечения]]
* [[Троичный поиск]]
* [[Полный перебор]]

== Литература ==
* {{книга
|подзаголовок
|заглавие=Искусство программирования, том 3. Сортировка и поиск
|оригинал=The Art of Computer Programming, vol.3. Sorting and Searching
|ссылка=
|автор=[[Дональд Кнут ]]
|издание = 2-е изд
|год=2007
|место=М.
|издательство= [[Вильямс (издательство)|«Вильямс»]]
|страницы= 824
|isbn= 0-201-89685-0
}}
{{нет сносок}}
[[Категория:Алгоритмы поиска]]