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

= (a1, a2, … , an ),
упорядоченный по возрастанию, т.е.

a1 ≤ a2 ≤ … ≤ an .

Найти: 1) Элемент с ключом Х;
2) Все элементы с ключом Х.

с ключом поиска «Х». Возможны варианты:
1) am = Х

элемент найден
2) am < Х продолжаем поиск в правой половине массива
3) am > Х продолжаем поиск в левой половине массива
Каким образом?

левая границы рабочей части массива,
Найден – логическая переменная,

в которой будем отмечать факт успешного завершения поиска.
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

4 5

6 7 8 9 10 11 12
а б б б в г д е ж з и к Х=б
L=1, R=12
1 2 3 4 5
а б б б в L=1, R=5


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

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

проверки на равенство.

⌊(L+R)/2⌋
IF (am < X) L: = m+1
ELSE R: =

m
FI
OD
IF (aR=X) Найден: = да
ELSE Найден: = нет
FI

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

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

случай, когда
1) часть массива aL , … , aR

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

А: Иванов Петров

Абрамов
223322 345767 667891

Struct abonent { char name[10];
long phone;
} A[n];

Чтобы отсортировать такой массив структур, нужно определить отношение порядка его элементов (> < =).

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

Эта запись не будет верной, т.к. компилятор не знает как сравнивать элементы типа структура, т.к. они не являются встроенными элементами языка.

( struct abonent X, struct abonent Y)
{ if ( X.name

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

чем нужно

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;
}

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

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

Аналогичное

переопределение операций сравнений требуется и для организации поиска!

от ключа сортировки и условия упорядочения данных.
2) Изменение направления упорядочения

массива легко достигается с помощью изменения знака в операции отношения на противоположный.

Операции пересылки не требуют переопределения,
т.к. выполняются путем побайтового копирования.

базы данных в памяти компьютера и мы хотим использовать его

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

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

индексный массив В,
в него записали номера элементов массива А

(по возрастанию элементов) и
обращаемся к элементам массива А
через индекс В.

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

…, 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

сортировки.
*Вначале в массив В записываются физические номера элементов массива А.

*Затем производится любая сортировка
при условии, что:
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

индексов, которые можно использовать по мере необходимости.

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

которые отвечают некоторым условиям.
Совокупность условий называется фильтром.
Пример. Из массива А

выбираем только четные элементы по возрастанию.
1 2 3 4 5 6 7 8
А : 5 7 3 4 2 6 1 8
D : 5 4 6 8 - только четные, по возрастанию