Существует массив, который может содержать, например, до 1000 элементы. Диапазон чисел, которые он может порождать, скажем 1 to 10^10. Теперь я должен найти minimal absolute difference между двумя числами в массиве. Я подумал о двух алгоритмах:
Для первого я определил функцию binarysearch, которая находит положение вставленного числа в отсортированном массиве. Теперь я запускаю отсортированный массив только с первым числом данного массива и начинаю итерирование по данному массиву со второго элемента вперед. Для каждого номера я нахожу его позицию в отсортированном массиве. Если число в этой позиции - это число, то разница равна 0, она является самой низкой возможной, поэтому я выхожу из цикла. Иначе я вставляю число в отсортированный массив в этой точке, затем проверяю разницу между этим числом и предыдущим и следующим числом в этом массиве. Затем я сохраняю минимум этого результата и предыдущего результата и продолжаю таким образом.
Во-вторых: я сортирую массив, используя quicksort. (Диапазон слишком велик, поэтому я думаю, что сортировка с помощью radix не будет такой эффективной). Затем я перебираю его, вырываясь с ответом 0, если два последовательных числа равны, иначе сохраняя минимум разницы между этим числом и предыдущим номером и предыдущим результатом.
Какой из них будет более эффективным?
Есть ли лучшее альго?
У Stackoverflow есть несколько сообщений в этом отношении, но они мало помогли. Здесь мой код в Perl:
sub position {
my @list = @{$_[0]};
my $target = $_[1];
my ($low,$high) = (0, (scalar @list)-1);
while ($low <= $high) {
$mid = int(($high + $low)/2);
if ( $list[$mid] == $target ) {
return $mid;
}
elsif ( $target < $list[$mid] ) {
$high = $mid - 1;
}
else {
$low = $mid + 1;
}
}
$low;
}
sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }
sub min { $_[0] > $_[1] ? $_[1] : $_[0]; }
$ans = 10_000_000_000;
@numbers = (234, 56, 1, 34...123); #given array
($max,$min) = @num[0, 0];
@sorted = ($numbers[0]);
for ( @num[1 .. $#num] ) {
$pos = position(\@sorted, $_);
if ( $sorted[$pos] == $_ ) {
$ans = 0;
last;
}
splice @sorted, $pos, 0, $_;
if ( $#sorted == $pos ) {
$ans = min($_-$sorted[-2], $ans);
}
elsif ( 0 == $pos ) {
$ans = min($sorted[1]-$_, $ans);
}
else {
$ans = min(min(abs($sorted[$pos-1]-$_), abs($sorted[$pos+1]-$_)), $ans);
}
$max = max($_, $max);
$min = min($_, $min);
}
print "$ans\n";
