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

Алгоритм

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

Берем средний элемент массива (обозначим его номер M) и сравниваем его с ключом. Возможны три исхода:

1) если средний элемент массива равен ключу, то искомый элемент найден;

2) если средний элемент массива меньше ключа, то все элементы массива с индексами, которые меньше M исключаются из рассмотрения;

3) если элемент массива больше ключа, то все элементы массива с индексами, которые больше M исключаются из рассмотрения;

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

1. Начальная установка: L = 1, R = N

2. Если R < L, то алгоритм окончен неудачно и перейти к шагу 7

3., в противном случае находим середину интервала [L; R] (M = (L+R)/2)

4. Если b<A[M], то перейти к шагу 5, если b>A[M], то перейти к шагу 6, если b=A[M], то алгоритм окончен удачно и перейти к шагу 7

5. Установить R=M-1, перейти к шагу 2

6. Установить L=M+1, перейти к шагу 2

7. Конец

Нахождение элемента бинарным поиском осуществляется очень быстро. При поиске среди N элементов требуется log2(N) сравнений в наихудшем случае. Кроме того, бинарный поиск уже при N порядка 100 значительно эффективнее линейного – как по скорости обнаружения, так и по способности к получению отрицательного результата. Для доказательства этого приведем следующие характеристики линейного и бинарного поиска:

поиск количество элементов среднее количество сравнений при наличии элемента количество сравнений при отсутствии элемента
линейный      
линейный      
линейный      
бинарный      
бинарный      
бинарный      

 

Алгоритмы поиска минимума (максимума)


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


<== предыдущая страница | следующая страница ==>
Алгоритм| З А Г А Д 1 страница

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