Двоичный поиск: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
→Поиск элемента в отсортированном массиве: исправлена пунктуация Метки: с мобильного устройства из мобильной версии |
→Поиск элемента в отсортированном массиве: Добавил пример на perl 5 Метки: с мобильного устройства из мобильной версии |
||
Строка 325:
}
</source>
{{конец скрытого блока}}
{{Начало скрытого блока
|Рамка =
|Ссылка = left
|Заголовок = Код на [[Perl]] 5
|Шрифт_заголовка = normal
|Наклон_заголовка = normal
|Фон_заголовка = #f9f9f9
|Выравнивание_заголовка = center
|Стиль заголовка =
|Шрифт_текста = normal
|Наклон_текста = normal
|Фон_текста = #ffffff
|Выравнивание_текста = left
|Стиль текста =
}}<source lang="perl">
use feature 'say';
#Искать случайные 10 чисел из ряда от 0 по 99:
my @seq = 0..99;
my @search = ();
push(@search, poprand(\@seq)) for 0..9;
#Создать последовательную случайную уникальную выборку 50 чисел из ряда от 0 по 99:
@seq = 0..99;
poprand(\@seq) for 0..49;
say "Что ищем:\n\t@search";
say "Где:\n\t@seq";
say '_' x ((scalar @seq + 1) * 3), "\n"; #Просто рисую линию, примерно длинны рада с пробелами и 2мя разрывами строки
map {
my $idx = bin_search(\@seq, $_);
printf "%s %s\n", $_, (defined $idx)?("находится на $idx месте"):("не найден"); #Места с 0 считаются
} @search;
#Извлечь случайное число из ряда. Для создания ряда нужно, с самим алгоритмом не связано
sub poprand{
my $seq = shift;
splice(@$seq, int(rand(scalar @$seq)), 1);
}
#Собственно, сам алгоритм поиска:
sub bin_search{
my ($lst, $x) = @_;
my @idx = (undef, $#{$lst}, 0); #0й элемент - текущий индекс; -1 - мин; 1 - макс
while($idx[-1] <= $idx[1]){
$idx[0] = int(($idx[-1] + $idx[1]) / 2);
return $idx[0] if $x == $lst->[$idx[0]];
($x < $lst->[$idx[0]])?
($idx[1] = $idx[0] - 1):
($idx[-1] = $idx[0] + 1);
}
return undef;
}
</source>
{{конец скрытого блока}}
| |||