рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Бинарный поиск в упорядоченных массивах

Бинарный поиск в упорядоченных массивах - Лекция, раздел Информатика, Двоичное кодирование информации. Физические, математические и информационные модели Едва Ли Не Самой Внушительной Демонстрацией Эффективности Применения Компьюте...

Едва ли не самой внушительной демонстрацией эффективности применения компьютеров являются задачи, в которых осуществляется поиск информации в некотором списке. Ранее мы использовали метод линейного (последовательного) поиска, суть которого заключается в последовательном просмотре всего списка элементов массива и сравнении значения очередного элемента с заданным для поиска. Этот метод поиска вполне эффективен на неупорядоченных массивах данных, а на предварительно отсортированных массивах значительно эффективнее выполнять поиск другими методами. Например, метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, так как занимает много времени.

Один из эффективных метод поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента. Такой метод можно проиллюстрировать на пример шуточного совета, как поймать в Африке льва: ″Для начала разделим Африку пополам. Ясно, что лев находится только в одной половине. Та половина, в которой находится лев, снова делится пополам и т.д. Площадь Африки приблизительно 30 млн. км2. Следовательно, после примерно 45 делений мы получим площадку, не превышающую 1 м2. Теперь на такой площадке льва поймать нетрудно″.

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

Составим программу, которая выполняет бинарный поиск заданного элемента в отсортированном массиве целых чисел, элементы которого имеют значения:

20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.

Введем в разделе описания констант размер массива Count=20 и опишем массив целых чисел:

M: array [1.. Count] of byte=20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.).

В разделе описания переменных опишем следующие переменные:

N-для хранения значения искомого элемента;

I-для указания очередного элемента массива;

First-указание индекса элемента - левой границы рассматриваемой части

массива;

Last-указание индекса элемента - правой границы рассматриваемой части

массива;

Found-логическая переменная, в которой будет записываться результат

поиска;

A-переменная, значение которой будет равно числу перестановок элементов.

В начале программы запишем вывод исходного массива на экран, затем вывод запроса искомого элемента, после чего считывание его значения в переменную N.

Перед началом поиска обнулим счетчик повторений А, установим левую и правую границы рассматриваемой части массива, а переменной Found присвоим значение False-элементы пока не найден. Данный фрагмент программы запишется так:

A: =0;

First: =1;

Last: = Count;

Found: =False;

Повторяющуюся процедуру бинарного поиска запишем с помощью оператора повтора repeat. Первый шаг бинарного поиска - деление исходного массива на две части можно записать так:

I: = (First+ Last) div 2

Условие поиска запишем оператором

if M[I]=N then Fond: = True

Если условие M[I]=N выполняется, то искомый элемент найден, переменной Found присваивается значение True, и управление передается за пределы оператора if. Если это условие не выполняется, то оператором

if M[I]>N then First: =I+1 else Last: =I-1;

проверяется условие M[I]>N. Если оно выполняется, значит значение искомого элемента расположено в правой части массива, поэтому левую границу части массива переносим в позицию I+1 (First: =I+1), иначе элемент нужно искать в левой части массива, а, значит правую границу части массива переносим в позицию I-1 (Last: =I-1). Затем нужно записать увеличение счетчика повторений при поиске A: =А+1. оператор повтора завершим записью условия окончания (Found) or (first>Last). Если это условие выполнится, т.е. если найдется искомый элемент или будет просмотрен весь массив, цикл завершится. Этот фрагмент программы можно записать так:

repeat

I: = (First+ Last) div 2;

if M[I]=N then Fond: = True

else

begin

if M[I]>N then First: =I+1;

else Last: =I-1;

end;

A: =А+1;

until (Found) or (First>Last);

{Повторить поиск}

{Разделить на две части}

{Искать элемент в правой части}

{Искать элемент в левой части}

{Увеличить счетчик числа итераций}

{Завершить, если найдется искомый элемент или будет просмотрен весь массив}

В заключительной части программы запишем условие вывода результата поиска. Если значение переменной Fond= True, то выведем на экран сообщение о том, какую позицию в массиве занимает искомый элемент, иначе выведем сообщение о том, что такого элемента в массиве нет. После чего выведем сообщение о том, сколько просмотров массива выполнялось в процессе поиска.

В целом текст программы будет записан следующим образом:

program Find Bin;

const

Count=s 20;

M: array [1.. Count] of byte=20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.).

var

N, I, First, Last Byte;

A: integer;

Fond: boolean;

Begin

Writeln (′Исходный массив :′);

for I:=1 to Count do Write(M[I]:3,′′);

Writeln;

Writeln;

Write(′Введите значение элемента массива для поиска>′);

Readln (N);

A: =0;

First: =1;

Last: = Count;

Found: =False; {Элемент не найден}

Repeat {Повторить поиск}

I: = (First+ Last) div 2;{Разделить на две части}

if M[I]=N then Fond: = True else

begin

if M[I]>N then First: =I+1{Искать элемент в правой части}

else Last: =I-1;{Искать элемент в левой части}

end;

A: =А+1; (Увеличить счетчик числа итераций)

until (Found) or (First>Last);(Завершить, если найдется искомый элемент или будет просмотрен весь массив}

if Found then Writeln(′Искомый элемент′,N,′в массиве занимает′ ,I,′-ю позицию′) else Writeln (′В массиве нет искомого элемента′,N);

Writeln (′Поиск выполнен за′, А, ′итераций′);

end.

Запустите интегрированную среду программирования. Введите текст программы Find_Bin и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того как компиляция выполнится успешно, запустите программу на исполнение в пошаговом режиме и наблюдайте изменения текущих значений переменных First, Last, I, M[I], а также значение выражений M[I]>N и (Found) or (First>Last). Обратите внимание на то, что бинарный поиск в сортированных массивах выполняется за небольшое число итераций.

 

– Конец работы –

Эта тема принадлежит разделу:

Двоичное кодирование информации. Физические, математические и информационные модели

Контрольные вопросы Дайте определение логики Какие высказывания называются ложными а какие истинными Какие логические связки.. Лекция Постановка цели.. Контрольные вопросы..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Бинарный поиск в упорядоченных массивах

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Лекция 1.
Тема: «Введение». 1. Информационная картина мира. Мы живем в мире, который существует в III основных формах: вещество, энергия, информация. Почему именно так, да

Лекция 2.
Тема: «Алгебра логики». Логика (от греческого слова «logos» - слово, мысль, речь, разум) – совокупность наук о законах и формах мышления, о наиболее общих

Лекция 3.
Тема: «Преобразование формул алгебры логики».   Постановка цели. 2) Устная работа. Какие из следующих предложений не являются объектами алг

Лекция 4.
Тема: «Система счисления». I. Система счисления – это совокупность приемов и правил для записи чисел цифровыми знаками. Существуют непозиционные и позиционные сис

Лекция 5.
Тема: «Перевод чисел из одной системы счисления в другую». 1) Перевод целых чисел. Чтобы перевести целое десятичное число, в двоичную (8-ю, 16-ю) систему с

Операция над двоичным числами
1. Сложение. При выполнении операции «+» можно пользоваться таблицей «+» двоичных цифр. Двоичное число 10 показывает, что при сложении в каком-нибудь разряде двух двоичных

Двоичная система счисления
Двоичная система используется в ЭВМ всех размеров, т.к. именно в двоичной форме внутри машины запоминается, перемещается из одного устройства в другое и перерабатывается вся информация. Обусловлено

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

Один и тот же объект может иметь множество моделей, а разные объекты могут описываться одной моделью
Все модели можно разбить на II больших класса: - модели предметные (материальные); - модели знаковые (информационные). Предметные модели воспроизводят геометрические, физ

Формы представления информационных моделей
1) Язык как средство информационного моделирования. Язык является знаковой системой, которая позволяет создавать информационные модели. Естественные языки используются

Лекция 8.
Тема: «Этапы решения задач с помощью ЭВМ». Подготовка любой задачи к решению на ЭВМ состоит из нескольких этапов. Все этапы взаимосвязаны. I этап – четкая формули

Лекция 9.
Тема: «Алгоритм и его свойства. Способы записи алгоритмов». I. Алгоритм и его свойства. Алгоритмом называется определенная, формальная, общеп

Лекция 10.
Тема: «Линейный алгоритм. Составление линейных алгоритмов» Если команды алгоритма выполняются последовательно, одна за другой, то такой алгоритм называется лине

Лекция 11.
Тема: «Разветвляющийся алгоритм».   В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгорит

Составление алгоритмов циклической и сложной структуры
1). Составить программу вычисления значения функции: а=1, b=2,2

Представление информации в компьютере
Компьютер может обрабатывать данные, которые представлены в специальном виде – только с помощью нулей и единиц. Каждый 0 или 1 называют битом. Один бит – это минимальная е

Внешняя память
В отличие от основной памяти внешняя память предназначена для долговременного хранения, и только хранения информации. Способность этой памяти хранить информацию не зависит от наличи

Краткая характеристика языка Паскаль
Язык программирования Паскаль разработан швейцарским профессором Высшей федеральной технической школы в Цюрихе, Н.Виртом в 1970 году. Затем в него были внесены несколько изменений и в 1979 году язы

Интегрированная среда программирования Turbo Pascal
Интегрированная среда программирования - IDE (Integrated Development Environment) включает в себя совокупность программ: экранный редактор, компилятор, компоновщик, отладчик, систему контекстной по

Клавиши оперативного вмешательства
Они представляют собой клавиши, которые устанавливаются для выполнения определенной функции, причем, находясь в любой точке среды Паскаль, нажатие клавиши Alt вместе с первой буквой любой команды и

File Edit Search Run Compile Debug Tools Options Window Help
File - работа с файлами; Debug - отладка; Edit - редактирование; Tools

Экранный редактор
Встроенный экранный редактор ТР предназначен для создания исходных текстов программ и их коррекции. В ТР 6.0 и 7.0 максимальный размер создаваемого файла – 1 Мбайт. Практически не ограничен размер

Основные команды перемещения
Команды управления перемещением курсора Ctrl-S, Ctrl-D, Ctrl-У и Ctrl-X позволяют свободно перемещаться по экрану без перехода на первый столбец в пустых стоках. Этот способ перемещения курсора осо

Символы языка
Паскаль использует следующие символы: 1. Буквы: 26 прописных латинских букв. 2. Цифры: 0,1,2,3,4,5,6,7,8,9. 3. Специальные символы: = + - * / <> () {} [] . , ; :

Лекция 16.
Тема: «Типы данных в языке программирования Turbo Pascal. Структура программы Turbo Pascal.» Типы данных в Паскале можно разделить на скалярны

Структура программы на языке Турбо Паскаль
Программа, написанная на языке Турбо Паскаль, имеет следующую структуру: · заголовок программы; · раздел описаний; · тело программы. Заголовок программы с

Лекция 17.
Тема: «Линейные программы» Строки программы, выполняемые одна за другой, называются линейными. Операторы языка. Операторы програм

Цикл FOR
Цикл FOR используется в трех случаях, когда число повторений может быть заранее известно. Существует две формы цикла: FOR i: =A TO B DO<тело цикла>

Понятие подпрограммы
Подпрограмма – это повторяющая группа операторов, оформленная в виде самостоятельной программой единицы. Она записывается однократно, а в соответствующих местах программы обеспечивается лишь обраще

Процедуры и функции
Цикл – это повторение группы операторов на данном этапе обработки информации. Если же какую-то группу одних и тех же команд требуется посторенние в разных местах программы, меняя лишь параметры, то

Операция над массивами
Инициализация. Инициализация-это присваивание компонентам массива начальных значений. Выполняется в цикле: FOR I: =1 TO 10 DO MASI [I]:=0 ;{ все элементы массива MASI равны 0}

Способы объявления двумерного массива
Способ 1. Если в программе используется один массива в разделе описания переменных: Var a: Array [1..n,..m] Of<тип элементов>; Спос

Сортировка массива
Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с о

Линейная сортировка (сортировка отбором)
Идея линейной сортировки по не возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом,

Сортировка методом пузырька
Один из самых популярных методов сортировки – ″пузырьковый″ метод основан на том, что в процессе исполнения алгоритма более ″легкие″ элементы массива

Графический экран
Отличие графического экрана от текстового: единица управления в графическом режиме - точка (пиксел), в текстовом – символ. Прежде чем работать с графическими командами, надо запустить графическую с

Текстовый экран
Текстовый экран позволяет разместить 25х80 символов. Минимальная единица управления - символ. Для управления цветом и фоном используются процедуры, находящиеся в модуле CRT: Cl

Управление звуком
Для создания звуковых эффектов используются процедуры модуля CRT: Sound(X)-звуковой сигнал частотой X герц; Delay (N)-задержка на N миллисекунд; NoSound-

Лекция 24.
Тема: «Операционные системы семейства Microsoft Windows». Windows- это название семейства операционных систем для IBM -совместимых персон

Основы взаимодействия пользователя с системой
После запуска системы Windows экран монитора приобретает специфическое оформление, называемое термином Рабочий стол.На нем размещаются значки-пиктограммыосновных п

Управление окнами
В основе системы Windowsтак же, как и других аналогичных систем, лежит понятие окна. Каждое окно имеет рамку и заголовок.Рамка использует

Навигация по дискам и каталогам с помощью пиктограммы
«Мой компьютер» пиктограмма «Мой компьютер» дает доступ к файловой системе ПК и позволяет запустить любое приложение. Для этого необходимо дважды щелкнуть значок «

Лекция 25.
Тема: «Запуск операционной системы. Работа с окнами, папкам и файлами». Для создания новой папки в приложении «Мой компьютер» нужно перейти в папку, где необходимо создать

Лекция 26.
Тема: «Основные возможности текстового редактора Word». В последнее время все большую популярность среди широкого круга пользователей завоевывает текстовый редактор Word д

Для отмены удаления
- на панели инструментов пиктографического меню нажать на кнопку с изображением изогнутой влево стрелки; - или использовать команду меню ПРАВКА – ОТМЕНИТЬ ВВОД. Добавление

Лекция 28.
Тема: «Работа с электронными таблицами в программе Excel». Для представления данных в удобном виде используют таблицы. Компьютер расширяет возможности использования таблиц

Ввод текста и чисел
Ввод текста осуществляется непосредственно в текущую ячейку или в строку формул, располагающуюся в верхней части окна программы непосредственно под панелями инструментов. Содержимое строки ф

Форматирование содержимого ячеек
Текстовые данные по умолчанию выравниваются по левому краю ячейки, а числа – по правому. Способ выполнения вычисления не зависит от того, каким способом данные отформатированы, но для человека внеш

Лекция 29.
Тема: «Диаграмма-графическое представление и редактирование данных». Большую помощь при обработке и анализе информации оказывает ее графическое представление. Это неудивит

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги