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

Сентябрь 5, 2022

Главная
Алгебра
Двоичный поиск в упорядоченном массиве

Содержание

3. Идея двоичного поиска: Возьмем средний элемент упорядоченного массива и сравним с ключом поиска «Х». Возможны варианты:
4. Алгоритм на псевдокоде (первая версия) Обозначим L, R – правая и левая границы рабочей части массива,
5. 1 2 3 4 5 6 7 8 9 10 11 12 а б б б
6. Рассмотрим вторую версию алгоритма, в которой уменьшим количество сравнений путем исключения из алгоритма проверки на равенство.
7. L: = 1, R: = n DO ( L m: = ⌊(L+R)/2⌋ IF (am ELSE R:
8. 1 2 3 4 5 6 7 8 9 10 11 12 а б б б
9. Трудоемкость двоичного поиска Сначала определим максимальное количество итераций (k). Рассмотрим худший случай, когда 1) часть массива
10. Трудоемкость двоичного поиска
12. Графики трудоемкости двоичного поиска
13. Сортировка данных со сложной структурой Дан массив абонентов А: Иванов Петров Абрамов 223322 345767 667891 Struct
14. Сортировка данных со сложной структурой Пример. Struct abonent { char name[10]; long phone; } A[n]; Попытка
16. Логическая функция Less (меньше) При сортировке по имени абонента: int less ( struct abonent X, struct
17. Наполовину пуст? Наполовину полон? Программист считает, что стакан в два раза больше, чем нужно
18. При сортировке по сложному ключу так же легко определить функцию less. Для сортировки по фамилии абонента
19. Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции less. Например, в пузырьковой сортировке: DO
20. Вывод: Если структура сортируемых данных не соответствует простым (встроенным) типам языка, то операции отношения необходимо переопределить
21. Преимущества: 1) Операции отношения могут быть определены различными способами в зависимости от ключа сортировки и условия
23. Сортировка по множеству ключей Пусть рассмотренный телефонный справочник хранится в виде базы данных в памяти компьютера
24. Индексация данных Рассмотрим суть индексации на массиве целых чисел: 1 2 3 4 5 6 7
25. Чтобы упорядочить массив А (по возрастанию), мы построили индексный массив В, в него записали номера элементов
26. Пример. Вывод элементов массива (по возрастанию): DO ( i = 1, …, n) вывод ( А
27. Построение индексного массива Построение индексного массива выполняется на базе любого алгоритма сортировки. *Вначале в массив В
28. Построение индексного массива Алгоритм на псевдокоде (на примере пузырьковой сортировки) B := (1, 2, …, n)
29. Преимущества индексации 1) Появляется возможность построения нескольких различных индексов, которые можно использовать по мере необходимости. 2)
31. Скачать презентацию

Слайд 2

Слайд 3

Идея двоичного поиска: Возьмем средний элемент упорядоченного массива и сравним с

ключом поиска «Х». Возможны варианты:
1) am = Х элемент найден
2) am < Х продолжаем поиск в правой половине массива
3) am > Х продолжаем поиск в левой половине массива
Каким образом?

Слайд 4

Алгоритм на псевдокоде (первая версия)
Обозначим
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

Слайд 5

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) находит первый попавшийся элемент из нескольких с заданным ключом.

Слайд 6

Рассмотрим вторую версию алгоритма,
в которой
уменьшим количество сравнений
путем

исключения из алгоритма
проверки на равенство.

Слайд 7

L: = 1, R: = n
DO ( L m: = ⌊(L+R)/2⌋
IF

(am < X) L: = m+1
ELSE R: = m
FI
OD
IF (aR=X) Найден: = да
ELSE Найден: = нет
FI

Алгоритм на псевдокоде (вторая версия)

Слайд 8

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) находит самый левый элемент среди тех, которые удовлетворяют ключу.

Слайд 9

Трудоемкость двоичного поиска
Сначала определим
максимальное количество итераций (k).
Рассмотрим худший случай,

когда
1) часть массива aL , … , aR содержит нечетное количество элементов
2) в начале каждой итерации
слева элементов на один больше
3) на каждом шаге выбирается левая часть массива.

Слайд 10

Трудоемкость двоичного поиска

Слайд 11

Слайд 12

Графики трудоемкости двоичного поиска

Слайд 13

Сортировка данных со сложной структурой
Дан массив абонентов
А: Иванов Петров Абрамов

223322 345767 667891
Struct abonent { char name[10];
long phone;
} A[n];
Чтобы отсортировать такой массив структур, нужно определить отношение порядка его элементов (> < =).

Слайд 14

Сортировка данных со сложной структурой
Пример. 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
Эта запись не будет верной, т.к. компилятор не знает как сравнивать элементы типа структура, т.к. они не являются встроенными элементами языка.

Слайд 15

Слайд 16

Логическая функция Less (меньше)
При сортировке по имени абонента:
int less (

struct abonent X, struct abonent Y)
{ if ( X.name else return 0;
}
При сортировке по номеру телефона абонента:
int less ( struct abonent X, struct abonent Y)
{ if ( X.phone else return 0;
}

Слайд 17

Наполовину пуст? Наполовину полон?
Программист считает, что
стакан в два раза больше, чем

нужно

Слайд 18

При сортировке по сложному ключу так же легко определить функцию 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;
}

Слайд 19

Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции 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

Слайд 20

Вывод:
Если структура сортируемых данных
не соответствует
простым (встроенным) типам языка, то

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

Слайд 21

Преимущества:
1) Операции отношения могут быть определены различными способами в зависимости от

ключа сортировки и условия упорядочения данных.
2) Изменение направления упорядочения массива легко достигается с помощью изменения знака в операции отношения на противоположный.
Операции пересылки не требуют переопределения,
т.к. выполняются путем побайтового копирования.

Слайд 22

Слайд 23

Сортировка по множеству ключей
Пусть рассмотренный телефонный справочник хранится в виде базы

данных в памяти компьютера и мы хотим использовать его для эффективного решения двух задач:
1) Быстро искать запись по заданной фамилии (справочник должен быть отсортирован по фамилиям абонентов);
2) Быстро искать запись по заданному номеру телефона (справочник должен быть отсортирован по номерам телефонов абонентов);
Для одновременного решения этих задач рассмотрим прием, называемый индексацией.

Слайд 24

Индексация данных
Рассмотрим суть индексации на массиве целых чисел:
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] ] – обращение к элементу массива А
через индекс С.

Слайд 25

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

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

Слайд 26

Пример. Вывод элементов массива (по возрастанию):
DO ( i = 1, …,

n)
вывод ( А [ В[i] ] )
OD
Пример. Двоичный поиск (вторая версия):
L: = 1, R: = n
DO ( L m: = ⌊(L+R)/2⌋
IF (А[В[m]] < X) L: = m+1
ELSE R: = m
FI
OD
IF (А[В[R]] = X) Найден: = да
ELSE Найден: = нет
FI

Слайд 27

Построение индексного массива
Построение индексного массива выполняется
на базе любого алгоритма сортировки.
*Вначале

в массив В записываются физические номера элементов массива А.
*Затем производится любая сортировка
при условии, что:
1) В операциях сравнения элементы массива А индексируются через В;
2) Перестановки делаются только в массиве В;

Слайд 28

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

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

Слайд 29

Преимущества индексации
1) Появляется возможность построения нескольких различных индексов, которые можно

использовать по мере необходимости.
2) Исключается копирование больших массивов данных.
3) Возможность
фильтрации данных.

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

Содержание

Идея двоичного поиска: Возьмем средний элемент упорядоченного массива и сравним с

Алгоритм на псевдокоде (первая версия)Обозначим L, R – правая и левая

1 2 3 4 5 6 7 8 9 10

Рассмотрим вторую версию алгоритма, в которой уменьшим количество сравнений путем

L: = 1, R: = n DO ( L m: = ⌊(L+R)/2⌋ IF

1 2 3 4 5 6 7 8 9 10

Трудоемкость двоичного поискаСначала определим максимальное количество итераций (k). Рассмотрим худший случай,

Трудоемкость двоичного поиска

Графики трудоемкости двоичного поиска

Сортировка данных со сложной структуройДан массив абонентов А: Иванов Петров Абрамов

Сортировка данных со сложной структуройПример. Struct abonent { char name[10];

Логическая функция Less (меньше)При сортировке по имени абонента: int less (

Наполовину пуст? Наполовину полон?Программист считает, что стакан в два раза больше, чем

При сортировке по сложному ключу так же легко определить функцию less.Для

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

Вывод:Если структура сортируемых данных не соответствует простым (встроенным) типам языка, то

Преимущества:1) Операции отношения могут быть определены различными способами в зависимости от

Сортировка по множеству ключейПусть рассмотренный телефонный справочник хранится в виде базы

Индексация данныхРассмотрим суть индексации на массиве целых чисел: 1 2 3

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

Пример. Вывод элементов массива (по возрастанию): DO ( i = 1, …,

Построение индексного массиваПостроение индексного массива выполняется на базе любого алгоритма сортировки.*Вначале

Построение индексного массива Алгоритм на псевдокоде (на примере пузырьковой сортировки) B

Преимущества индексации 1) Появляется возможность построения нескольких различных индексов, которые можно

Похожие презентации

Алгоритм на псевдокоде (первая версия)
Обозначим
L, R – правая и левая

Рассмотрим вторую версию алгоритма,
в которой
уменьшим количество сравнений
путем

L: = 1, R: = n
DO ( L m: = ⌊(L+R)/2⌋
IF

Трудоемкость двоичного поиска
Сначала определим
максимальное количество итераций (k).
Рассмотрим худший случай,

Сортировка данных со сложной структурой
Дан массив абонентов
А: Иванов Петров Абрамов

Сортировка данных со сложной структурой
Пример. Struct abonent { char name[10];

Логическая функция Less (меньше)
При сортировке по имени абонента:
int less (

Наполовину пуст? Наполовину полон?
Программист считает, что
стакан в два раза больше, чем

При сортировке по сложному ключу так же легко определить функцию less.
Для

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

Вывод:
Если структура сортируемых данных
не соответствует
простым (встроенным) типам языка, то

Преимущества:
1) Операции отношения могут быть определены различными способами в зависимости от

Сортировка по множеству ключей
Пусть рассмотренный телефонный справочник хранится в виде базы

Индексация данных
Рассмотрим суть индексации на массиве целых чисел:
1 2 3

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

Пример. Вывод элементов массива (по возрастанию):
DO ( i = 1, …,

Построение индексного массива
Построение индексного массива выполняется
на базе любого алгоритма сортировки.
*Вначале

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

B

Преимущества индексации
1) Появляется возможность построения нескольких различных индексов, которые можно