Поиск c барьером
в упорядоченной последовательности
x= 11
x= 9
BARRIER_SORTED(a, x)
1i ← 1
2an+1 ← x
3while ai < x do
4i ← i +
5 if ai ≠ x или n then i ← 0
6return i
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
11 |
x |
x |
x |
x |
x |
x |
x |
x |
|
|
|
|
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
9 |
x |
x |
x |
x |
x |
x |
x |
|
|
|
|
|
21
Алгоритм поиска с барьером в упорядоченной последовательности (худший случай)
Поиск последнего |
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 11 14 16 16 |
элемента |
x |
x |
x |
x |
x |
x |
x |
x х х |
|
Поиск несуществующего |
1 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
18 |
|
элемента, который |
||||||||||||
x |
|
x |
x |
x |
x |
x |
x |
x |
x |
|
||
больше последнего |
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
Поведение алгоритма поиска с барьером в худшем случае одинаково как для упорядоченной, так и для неупорядоченной последовательностей и составляет O(n+1).
22
Алгоритм поиска с барьером в упорядоченной последовательности (средний случай)
Возможно два средних случая:
1.Поиск всегда завершается успешно, то есть искомый элемент всегда присутствует в последовательности a. В данном случае считается, вероятность появления каждого элемента последовательности на входе алгоритма одинакова. В данном случае средняя вычислительная сложность не отличается от алгоритма последовательного
Tсб1 (ср) 1 i 1 |
n(n 1) |
n 1 |
n |
|
|
n i 0 n |
2 |
2 |
2.Поиск может окончиться неудачей. Существует некоторый диапазон R значений, каждое из которых равновероятно, при этом последовательность состоит из некоторых элементов этого диапазона.
23
Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (2)
Рассмотрим 3 частных случая распределения элементов последовательности a по диапазону допустимых значений R
1. Точки сосредоточены в начале диапазона R
a1 a2 an
. . .
R
2. Точки равномерно распределены по диапазону R
R / (n+1) |
a2 |
an |
|
||
a1 |
|
. . . |
3. Точки сосредоточены в конце диапазона R |
||
|
|
a1 a2 an |
|
|
. . . |
24
Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (3)
1. Точки сосредоточены в начале диапазона R |
|
||||||||
|
a1 a2 |
an |
|
|
|
|
|||
|
|
|
. . . |
|
|
|
|
|
|
|
n T1 |
|
R n |
R |
R n |
|
|||
T 2 |
|
(n 1) n n 1 |
(n 1) |
||||||
сб (сp) |
R |
сб (сp) |
|
|
R |
R 2 |
R |
|
|
(n 1) n |
|
R n |
(n 1) 2R n |
|
|
||||
|
|
|
R |
|
|
2R |
|
|
|
|
2R |
|
|
|
|
|
|||
|
|
2R |
|
n |
n 1 |
|
|
||
lim (n 1) |
|
2R |
|
|
|
|
|||
R |
|
|
|
|
|
|
|
|
|
25
Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (3)
3. Точки сосредоточены в конце диапазона R
a1 a2 an
. . .
T 2 |
|
n |
T1 |
|
|
R n |
1 |
n |
n 1 |
|
R n |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
сб (сp) |
|
R сб (сp) |
|
|
R |
|
|
|
|
|
|
R 2 |
|
|
R |
|
|
|
|
|
|
|
|||
n2 n 2R 2n |
|
n2 |
n 2R 2n |
|
2R n2 |
n |
1 |
n2 n |
|||||||||||||||||
|
2R |
|
|
|
|
|
|
2R |
|
|
2R |
|
2R |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
n2 n |
1, |
R |
f (n) n |
2 |
|
lim |
|
|
n2 n |
1,5 |
|||||||||||||
lim 1 |
|
|
|
|
|
1 |
|
2 |
|
||||||||||||||||
|
|
2R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2n |
|
|
|
|
|
R |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
n |
2 |
|
n |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
R f (n) n |
lim 1 |
|
|
2n |
|
1 n |
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
26
Алгоритм поиска с барьером в упорядоченной последовательности (средний случай) (3)
2. Точки равномерно распределены по диапазону R
n + 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
a |
|
|
a |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
a |
|
1 |
|
2 |
|
n |
|||
|
|
|
|||||||
|
|
|
|||||||
|
|
|
|||||||
|
|
|
|||||||
|
|
|
|
||||||
|
|
|
|
|
|
. . .
R / (n+1)
2 |
n 1 |
|
|
R 1 |
|
1 |
n 1 |
1 (n 1)(n 2) |
|
(n 2) |
|||||
Tсб (сp) i |
|
|
|
|
|
|
i |
|
|
|
|
|
|||
|
|
|
n 1 |
2 |
2 |
||||||||||
|
i 1 |
|
n 1 R |
|
n 1 i 1 |
|
|||||||||
27
Сравнение алгоритмов поиска
1. Последовательный поиск
2 |
2Rn n2 n |
lim |
2Rn n2 n |
|
n n2 |
Tп(ср) |
|
|
lim n |
|
|
|
2R |
|
2R |
|
2R |
|
R |
R |
2. Поиск с барьером в отсортированной последовательности
1) |
Точки сосредоточены в нача |
диапазона R |
|
|
|||
|
2 |
2R n |
|
(n 1) |
2R n |
n 1 |
|
|
Tсб (сp) (n 1) |
2R |
lim |
2R |
|
||
|
|
R |
|
|
|
||
2) |
Точки равномерно распределены по диапазону R |
||||||
T 2 |
|
(n 2) |
n |
1 |
|
|
|||
|
|
|
|||||||
сб (сp) |
|
|
2 |
2 |
|
|
|
||
3) Точки сосредоточены в конце диапазона R |
|||||||||
2 |
|
|
|
n2 |
n |
|
n2 n |
1 |
|
Tсб (сp) 1 |
|
|
|
lim 1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2R |
R |
2R |
|
||
n
28
Бинарный поиск
Искомый элемент x = 10
1.В рассматриваемом диапазоне [l; u] ([1; 12]) центральный элемент с
номером i = l + [(u – l)/2] сравнивается с x. Если ai = x, то поиск завершен успешно, иначе, если l = u, то поиск завершен неудачно.
Иначе, если ai < x, то продолжить поиск для диапазона [i + 1; u], иначе (если ai > x) – продолжить поиск для диапазона [l; i – 1].
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
12 |
|
||
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
|
16 |
18 |
l = 1, u = 12, 1+[(12-1)/2] = 6 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
||
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
18 |
l = 7, u = 12, 7+[(12-7)/2] = 9 |
||
x |
x |
x |
x |
x |
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
||
1 |
2 |
3 |
4 |
5 |
7 |
8 |
10 |
11 |
14 |
16 |
18 |
l = 7, u = 8, 7+[(8-7)/2] = 7 |
||
x |
x |
x |
x |
x |
x |
|
|
|
x |
x |
x |
x |
|
|
29
Бинарного поиск (2)
Искомый элемент x = 9
1 2 3 4 5
1 
2 
3 
4 
5
1 2 3 4 5
1 
2 
3 
4 
5 x x x x x
1 2 3 4 5
1 
2 
3 
4 
5 x x x x x
1 2 3 4 5
1 
2 
3 
4 
5 x x x x x
6 |
7 |
8 |
9 |
10 |
11 |
12 |
7 
8 
10 
11 
14 
16 
18 
6 |
7 |
8 |
9 |
10 |
11 |
12 |
7 
8 
10 
11 
14 
16 
18 
x
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
7 |
8 |
10 |
11 |
14 |
16 |
18 |
|
x |
|
|
|
x |
x |
x |
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
7 |
8 |
10 |
11 |
14 |
16 |
18 |
|
x |
|
|
x |
x |
x |
x |
x |
l = u, al ≠ x |
l = 1, u = 12, 1+[(12-1)/2] = 6
l = 7, u = 12, 7+[(12-7)/2] = 9
l= 7, u = 8, 7+[(9-7)/2] = 7
l= 8, u = 8, 7+[(8-8)/2] = 8
30