Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Алгоритм. Алгоритмы поиска (поиск в массиве: линейный, с барьером

Читайте также:
  1. Алгоритм
  2. Алгоритм
  3. Алгоритм 11.1. Контроль столкновений с помощью описанных прямоугольников.
  4. Алгоритм 13.1. Алгоритм Преследования.
  5. Алгоритм 13.2. Алгоритм Уклонения.
  6. Алгоритм 13.3. Шаблоны со случайным выбором.

Алгоритмы поиска (поиск в массиве: линейный, с барьером, бинарный поиск в упорядоченном массиве, поиск минимума, максимума в массиве).

Линейный поиск в массиве

Постановка задачи

Пусть дан массив элементов A и ключ b. Необходимо выяснить, имеется ли в массиве A элемент, совпадающий по значению с ключом b.

Алгоритм

Линейный поиск подразумевает последовательный просмотр всех элементов массива А в порядке их расположения, пока не найдется элемент равный b. Если заранее неизвестно, имеется данный элемент в массиве или нет, то необходимо следить за тем, чтобы поиск не вышел за границы массива, что можно реализовать без использования и с использованием барьерного элемента.

Алгоритм без использования барьерного элемента

  1. Установить I = 1
  2. Если A[I] = b, элемент найден (алгоритм закончен удачно), перейти к шагу 5
  3. Увеличить I на 1
  4. Если I £ N, то перейти к шагу 2. В противном случае алгоритм окончен неудачно.
  5. Конец

Алгоритм с использованием барьерного элемента. Искомый элемент b помещаем в массив на (N+1)-е место, таким образом этот элемент всегда в массиве будет найден, вопрос только в том, на каком месте мы его нашли. Если нашли на (N+1)-м месте, то это означает, что такого элемента в массиве нет, иначе его номер в массиве меньше или равен N.

Алгоритм поиска с барьером

  1. Установить I = 1
  2. Если A[I] = b, элемент найден, перейти к шагу 5
  3. Увеличить I на 1
  4. Перейти к шагу 2
  5. Если I £ N, то элемент в массиве есть, иначе элемента в массиве нет.
  6. Конец

Сложность алгоритма поиска естественно оценивать по числу сравнений элементов массива с искомым элементом.

Следует отметить, что в общем случае при линейном поиске среди N элементов требуется в среднем N сравнений в случае успешного поиска и 2*N сравнений в наихудшем случае.
При линейном поиске с барьером среди N элементов требуется в среднем N/2 сравнений в случае успешного поиска и N сравнений в наихудшем случае.
Затраты времени для больших массивов в обоих случаях велики. Применяется алгоритм линейного поиска (с барьером или без), если никакой дополнительной информации о данных массива нет.


Дата добавления: 2015-07-12; просмотров: 345 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Алгоритм 3. Записать коэффициенты разложения, основания степеней и показатели степеней в системе с основанием Q и выполнить все действия в этой самой системе.| Алгоритм

mybiblioteka.su - 2015-2024 год. (0.007 сек.)