18
{
int m, left = 0, right = a.Length - 1;
do
{
m = (left + right) / 2;
if (x > a[m])
left = m + 1;
else
right = m - 1;
}
while ((a[m] != x) && (left <= right));
if (a[m] == x)
return m;
else
return -1;
}
Данный алгоритм по сравнению с предыдущим обладает гораздо более
высокой скоростью выполнения. Его временная эффективность характеризу-
ется скоростью роста
O(log
2
N).
2.2. А
ЛГОРИТМЫ СОРТИРОВКИ
Основным требованием к методам сортировки массивов является эко-
номное использование памяти. Это означает, что переупорядочение элемен-
тов необходимо выполнять
in situ (на том же месте). Поэтому основным кри-
терием эффективности алгоритма сортировки является его быстродействие.
При сортировке элементов в массиве выполняются две основных операции:
сравнения элементов по ключу сортировки и пересылка элементов. И число
сравнений, и число перестановок зависят от размера массива
N.
Хорошие алгоритмы
сортировки требуют порядка N*log
2
N
сравне-
ний, более простые – порядка
N
2
сравнений ключей. Как правило, усовершен-
ствованные алгоритмы сортировки содержат меньшее число операций, одна-
ко это достигается путем усложнения самих операций. Поэтому простые ме-
тоды являются
предпочтительными при малых N, но
их не рекомендуется
использовать для сортировки массивов больших размеров.
18 / 23
19
При выборе того или иного алгоритма сортировки для конкретной за-
дачи необходимо учитывать ряд условий. Перечислим
наиболее важные из
них.
Do'stlaringiz bilan baham: 
