Последовательный поиск

⇐ Предыдущая 1 2 3 4 5 6 789 10 Следующая ⇒

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

Последовательный (или линейный) поиск – наиболее просто реализуемый метод поиска.

Последовательный поиск заключается в последовательном переборе элементов структуры данных (например, массива) от начального элемента до нахождения совпадения или до конца структуры данных. Перебор элементов имеет линейный хпрактер, поэтому такой поиск ещё называют линейным.

Примеры последовательного поиска с циклами for и while.

Программа линейного поиска на языке "Паскаль" var nums: array [0..N] of real; function search_s1(item: ^real; n: integer; key: real):integer; var i: integer; begin for i:= 0 to N do if key = item[i] then begin search_s1:= i; break end else search_s1:= -1 end; function search_s2(item: ^real; n: integer; key: real):integer; var i: integer; begin i:=0; search_s2:= -1; while (key <> item[i]) or (i < n) do begin if key = item[i] then search_s2:= i; i:= i + 1 end end;

Аналогичные процедуры на языке Си++:
int search_s1(float* item, int n, float key)
{
for (int i = 0; i < N; i++)
if (key == item[i])
return i;
return -1;
}

int search_s2(float* item, int n, float key)
{
int i=0;
while (key!= item[i] || i < n)
{
if (key == item[i])
return i;
i++;
}
return -1;
}

Последовательный поиск в среднем случае выполнит проверку N/2 элементов, в лучшем – 1 элемента, а в худшем – N элементов.

Недостаток этого поиска – медленное выполнение при большом объеме просматриваемого массива.

Но если данные не отсортированы, то должен использоваться только последовательный поиск.

⇐ Предыдущая 1 2 3 4 5 6 789 10 Следующая ⇒

Дата добавления: 2015-09-04; просмотров: 448. Нарушение авторских прав; Мы поможем в написании вашей работы!

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

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

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Тема: Кинематика поступательного и вращательного движения. 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью, проекция которой изменяется со временем 1. Твердое тело начинает вращаться вокруг оси Z с угловой скоростью...

Условия приобретения статуса индивидуального предпринимателя. В соответствии с п. 1 ст. 23 ГК РФ гражданин вправе заниматься предпринимательской деятельностью без образования юридического лица с момента государственной регистрации в качестве индивидуального предпринимателя. Каковы же условия такой регистрации и...

Седалищно-прямокишечная ямка Седалищно-прямокишечная (анальная) ямка, fossa ischiorectalis (ischioanalis) – это парное углубление в области промежности, находящееся по бокам от конечного отдела прямой кишки и седалищных бугров, заполненное жировой клетчаткой, сосудами, нервами и...

Образование соседних чисел Фрагмент: Программная задача: показать образование числа 4 и числа 3 друг из друга...

Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Краткая психологическая характеристика возрастных периодов.Первый критический период развития ребенка — период новорожденности Психоаналитики говорят, что это первая травма, которую переживает ребенок, и она настолько сильна, что вся последующая жизнь проходит под знаком этой травмы...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия