Презентация - Двоичный поиск в упорядоченном массиве

Смотреть слайды в полном размере
Презентация Двоичный поиск в упорядоченном массиве


Вашему вниманию предлагается презентация на тему «Двоичный поиск в упорядоченном массиве», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 30 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 722.21 KB

Просмотреть и скачать

Pic.1
Двоичный поиск в упорядоченном массиве Пусть дан массив А = (a1, a2, … , an ), упорядоченный по возр
Двоичный поиск в упорядоченном массиве Пусть дан массив А = (a1, a2, … , an ), упорядоченный по возрастанию, т. е. a1 ≤ a2 ≤ … ≤ an . Найти: 1) Элемент с ключом Х; 2) Все элементы с ключом Х.
Pic.2
Если массив не упорядочен, то единственный способ поиска – перебор, трудоемкость О(n). Если массив н
Если массив не упорядочен, то единственный способ поиска – перебор, трудоемкость О(n). Если массив не упорядочен, то единственный способ поиска – перебор, трудоемкость О(n). В случае быстрого двоичного поиска трудоемкость О().
Pic.3
Идея двоичного поиска: Возьмем средний элемент упорядоченного массива и сравним с ключом поиска «Х».
Идея двоичного поиска: Возьмем средний элемент упорядоченного массива и сравним с ключом поиска «Х». Возможны варианты: 1) am = Х элемент найден 2) am < Х продолжаем поиск в правой половине массива 3) am > Х продолжаем поиск в левой половине массива Каким образом?
Pic.4
Алгоритм на псевдокоде (первая версия) Обозначим L, R – правая и левая границы рабочей части массива
Алгоритм на псевдокоде (первая версия) Обозначим L, R – правая и левая границы рабочей части массива, Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска. L: = 1, R: = n, Найден: = нет DO ( L ≤ R ) m: = ⌊(L+R)/2⌋ IF (am=X) Найден: =да OD FI IF (am < X) L: = m+1 ELSE R: = m-1 FI OD
Pic.5
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 а б б б в г д е ж з и к Х=б L=1, R=12 1 2 3 4
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 а б б б в г д е ж з и к Х=б L=1, R=12 1 2 3 4 5 а б б б в L=1, R=5 Недостатки первой версии алгоритма: 1) на каждой итерации цикла два сравнения, 2) находит первый попавшийся элемент из нескольких с заданным ключом.
Pic.6
Рассмотрим вторую версию алгоритма, Рассмотрим вторую версию алгоритма, в которой уменьшим количеств
Рассмотрим вторую версию алгоритма, Рассмотрим вторую версию алгоритма, в которой уменьшим количество сравнений путем исключения из алгоритма проверки на равенство.
Pic.7
Алгоритм на псевдокоде (вторая версия) L: = 1, R: = n DO ( L<R ) m: = ⌊(L+R)/2⌋ IF (am < X) L:
Алгоритм на псевдокоде (вторая версия) L: = 1, R: = n DO ( L<R ) m: = ⌊(L+R)/2⌋ IF (am < X) L: = m+1 ELSE R: = m FI OD IF (aR=X) Найден: = да ELSE Найден: = нет FI
Pic.8
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 а б б б в г д е ж з и к Х=б L=1, R=12 1 2 3 4
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 а б б б в г д е ж з и к Х=б L=1, R=12 1 2 3 4 5 6 а б б б в г L=1, R=6 1 2 3 а б б L=1, R=3 1 2 а б L=1, R=2 2 б L=2, R=2 Преимущества второй версии алгоритма: 1) на каждой итерации цикла одно сравнение, 2) находит самый левый элемент среди тех, которые удовлетворяют ключу.
Pic.9
Трудоемкость двоичного поиска Сначала определим максимальное количество итераций (k). Рассмотрим худ
Трудоемкость двоичного поиска Сначала определим максимальное количество итераций (k). Рассмотрим худший случай, когда 1) часть массива aL , … , aR содержит нечетное количество элементов 2) в начале каждой итерации слева элементов на один больше 3) на каждом шаге выбирается левая часть массива.
Pic.10
Трудоемкость двоичного поиска Номер итерации Наибольшее количество элементов 0 n - нечетное 1 = 2 =
Трудоемкость двоичного поиска Номер итерации Наибольшее количество элементов 0 n - нечетное 1 = 2 = 3 = … … k-1 = 2
Pic.11
2 2 2 < n k-1 < k < +1 k - количество итераций С +1 Трудоемкость двоичного поиска: Т = О()
2 2 2 < n k-1 < k < +1 k - количество итераций С +1 Трудоемкость двоичного поиска: Т = О()
Pic.12
Графики трудоемкости двоичного поиска
Графики трудоемкости двоичного поиска
Pic.13
Сортировка данных со сложной структурой Дан массив абонентов А: Иванов Петров Абрамов 223322 345767
Сортировка данных со сложной структурой Дан массив абонентов А: Иванов Петров Абрамов 223322 345767 667891 Struct abonent { char name[10]; long phone; } A[n]; Чтобы отсортировать такой массив структур, нужно определить отношение порядка его элементов (> < =).
Pic.14
Сортировка данных со сложной структурой Пример. Struct abonent { char name[10]; long phone; } A[n];
Сортировка данных со сложной структурой Пример. Struct abonent { char name[10]; long phone; } A[n]; Попытка сортировки: DO ( i = 1, 2, …, n-1 ) DO ( j = n, n-1, …, i+1) IF ( Aj < Aj-1 ) Aj ↔ Aj-1 FI OD OD Эта запись не будет верной, т. к. компилятор не знает как сравнивать элементы типа структура, т. к. они не являются встроенными элементами языка.
Pic.15
Чтобы реализовать операцию сравнения для структур, необходимо вспомнить, что любая операция отношени
Чтобы реализовать операцию сравнения для структур, необходимо вспомнить, что любая операция отношения есть булева функция двух аргументов. Чтобы реализовать операцию сравнения для структур, необходимо вспомнить, что любая операция отношения есть булева функция двух аргументов. X<Y меньше (X, Y) = Логическая функция Less (меньше) может выглядеть следующим образом: Int less ( struct abonent X, struct abonent Y) { … ? … }
Pic.16
Логическая функция Less (меньше) Логическая функция Less (меньше) При сортировке по имени абонента:
Логическая функция Less (меньше) Логическая функция Less (меньше) При сортировке по имени абонента: int less ( struct abonent X, struct abonent Y) { if ( X. name<Y. name) return 1; else return 0; } При сортировке по номеру телефона абонента: int less ( struct abonent X, struct abonent Y) { if ( X. phone<Y. phone) return 1; else return 0; }
Pic.17
Наполовину пуст? Наполовину полон?
Наполовину пуст? Наполовину полон?
Pic.18
При сортировке по сложному ключу так же легко определить функцию less. При сортировке по сложному кл
При сортировке по сложному ключу так же легко определить функцию less. При сортировке по сложному ключу так же легко определить функцию less. Для сортировки по фамилии абонента и (дополнительно) по номеру телефона: int less ( struct abonent X, struct abonent Y) { if ( X. name < Y. name) return 1; else if ( X. name > Y. name) return 0; else if ( X. phone < Y. phone) return 1; else return 0; }
Pic.19
Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции less. Тогда в алго
Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции less. Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции less. Например, в пузырьковой сортировке: DO ( i = 1, 2, …, n-1) DO ( j = n, n-1, …, i+1) IF ( less ( Aj , Aj-1 ) ) Aj ↔ Aj-1 FI OD OD
Pic.20
Вывод: Вывод: Если структура сортируемых данных не соответствует простым (встроенным) типам языка, т
Вывод: Вывод: Если структура сортируемых данных не соответствует простым (встроенным) типам языка, то операции отношения необходимо переопределить с помощью соответствующих булевых функций. Аналогичное переопределение операций сравнений требуется и для организации поиска!
Pic.21
Преимущества: Преимущества: 1) Операции отношения могут быть определены различными способами в завис
Преимущества: Преимущества: 1) Операции отношения могут быть определены различными способами в зависимости от ключа сортировки и условия упорядочения данных. 2) Изменение направления упорядочения массива легко достигается с помощью изменения знака в операции отношения на противоположный. Операции пересылки не требуют переопределения, т. к. выполняются путем побайтового копирования.
Pic.22
Двоичный поиск в упорядоченном массиве, слайд 22
Pic.23
Сортировка по множеству ключей Пусть рассмотренный телефонный справочник хранится в виде базы данных
Сортировка по множеству ключей Пусть рассмотренный телефонный справочник хранится в виде базы данных в памяти компьютера и мы хотим использовать его для эффективного решения двух задач: 1) Быстро искать запись по заданной фамилии (справочник должен быть отсортирован по фамилиям абонентов); 2) Быстро искать запись по заданному номеру телефона (справочник должен быть отсортирован по номерам телефонов абонентов); Для одновременного решения этих задач рассмотрим прием, называемый индексацией.
Pic.24
Индексация данных Рассмотрим суть индексации на массиве целых чисел: 1 2 3 4 5 6 7 8 - физические но
Индексация данных Рассмотрим суть индексации на массиве целых чисел: 1 2 3 4 5 6 7 8 - физические номера А: 5 7 3 4 2 6 1 8 В: 7 5 3 4 1 6 2 8 1 2 3 4 5 6 7 8 - логические номера Массив В - индексный массив (индекс) массива А. А [ B[i] ] – обращение к элементу массива А через индекс В. С: 8 2 6 1 4 3 5 7 - номера элементов массива А по убыванию Массив С – индексный массив (индекс) массива А. А [ С[i] ] – обращение к элементу массива А через индекс С.
Pic.25
Чтобы упорядочить массив А (по возрастанию), Чтобы упорядочить массив А (по возрастанию), мы построи
Чтобы упорядочить массив А (по возрастанию), Чтобы упорядочить массив А (по возрастанию), мы построили индексный массив В, в него записали номера элементов массива А (по возрастанию элементов) и обращаемся к элементам массива А через индекс В. При доступе к массиву А через индекс мы работаем с ним как с упорядоченным (например, можем производить быстрый двоичный поиск), в то время как сами элементы физически не переставляются.
Pic.26
Пример. Вывод элементов массива (по возрастанию): Пример. Вывод элементов массива (по возрастанию):
Пример. Вывод элементов массива (по возрастанию): Пример. Вывод элементов массива (по возрастанию): DO ( i = 1, …, n) вывод ( А [ В[i] ] ) OD Пример. Двоичный поиск (вторая версия): L: = 1, R: = n DO ( L<R ) m: = ⌊(L+R)/2⌋ IF (А[В[m]] < X) L: = m+1 ELSE R: = m FI OD IF (А[В[R]] = X) Найден: = да ELSE Найден: = нет FI
Pic.27
Построение индексного массива Построение индексного массива выполняется на базе любого алгоритма сор
Построение индексного массива Построение индексного массива выполняется на базе любого алгоритма сортировки. *Вначале в массив В записываются физические номера элементов массива А. *Затем производится любая сортировка при условии, что: 1) В операциях сравнения элементы массива А индексируются через В; 2) Перестановки делаются только в массиве В;
Pic.28
Построение индексного массива Алгоритм на псевдокоде (на примере пузырьковой сортировки) B := (1, 2,
Построение индексного массива Алгоритм на псевдокоде (на примере пузырьковой сортировки) B := (1, 2, …, n) DO ( i = 1, 2, …, n-1) DO ( j = n, n-1, …, i+1) IF ( a[ bj ] < a[ bj-1 ]) bj↔bj-1 FI OD OD
Pic.29
Преимущества индексации 1) Появляется возможность построения нескольких различных индексов, которые
Преимущества индексации 1) Появляется возможность построения нескольких различных индексов, которые можно использовать по мере необходимости. 2) Исключается копирование больших массивов данных. 3) Возможность фильтрации данных.
Pic.30
Преимущества индексации Определение. Фильтрация – использование при работе только тех элементов, кот
Преимущества индексации Определение. Фильтрация – использование при работе только тех элементов, которые отвечают некоторым условиям. Совокупность условий называется фильтром. Пример. Из массива А выбираем только четные элементы по возрастанию. 1 2 3 4 5 6 7 8 А : 5 7 3 4 2 6 1 8 D : 5 4 6 8 - только четные, по возрастанию


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!