А.Ф. Деон, Ю.И. Терентьев
6
Int z = ( n1 + n2 ) >> 1; // середина интервала поиска
if( a[j] == a[z] ) { n1 = z; break; } // число найдено
if( a[j] < a[z] ) n2 = z — 1; // продолжить поиск слева
else n1 = z + 1; // продолжить поиск справа
}
return n1; // место вставки
}
//------------------------------------------------------
--------
void SortInsertDich( int a[], const int n )
{
for( int j = 1; j < n; j++ ) // цикл исходных элементов
{
if( a[j-1] <= a[j] ) continue; // вставка не нужна
int i = DichPos( a, j ); // местo вставки
int r = a[j]; // запомнить вставляемый элемент
for( int m = j; m > i; m-- ) a[m] = a[m-1]; // сдвиг
a[i] = r; // установить текущий максимальный элемент
}
}
Прежде чем выяснять маргинальные свойства функции
Sort-
InsertDich()
, займемся функцией дихотомического поиска
DichPos()
.
На первом этапе определим количество операций, необходимых для
инструкции
int n
1
=
0
, n
2
= n –
1:
1
1 2 3
W
= + =
.
На втором этапе дихотомический поиск контролирует заголовок
цикла с предусловием
while( n1 <= n2 )
, затрачивая на определение
истинности условия
n
1
<= n
2 одну операцию на каждой итерации.
Количество итераций зависит от расположения информации в
элементах массива. Маргинальные оценки дают два варианта. Поиск
обнаружил элемент сразу за одну итерацию. Это значит, что элемент
поиска находится посредине поступившего массива. Обозначим
такое количество операций на втором этапе как
2,1min
1
W
=
.
Максимальное количество итераций определяется логарифмом с
округлением в бо́
льшую сторону (обозначается внешними квадрат-
ными скобками):
1,2max
2
2
1]log [ ]log [
W
n
n
= ⋅
=
.
В теле цикла определяется индекс элемента, находящегося между
граничными элементами
n1
и
n2
. На вычисление этого индекса в ин-
струкции
z =
(
n
1
+ n
2)
>>
1 затрачиваются три операции. Можно
