StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POBest algorithm to find the minimum absolute difference between two numbers in an array
text
Body
copied!<p>There is an array which can contain, say, upto <code>1000</code> elements. The range of numbers it can spawn is say <code>1 to 10^10</code>. Now I have to find the <code>minimal absolute difference</code> between two numbers in the array. I have thought of two algorithms: </p> <p><strong>For the first one</strong>, I have defined a <code>binarysearch</code> function which finds the position of a to-be-inserted number in a sorted array. Now I start the sorted array with only the first number of the given array and begin iterating on the given array from the second element onwards. For each number, I find its position in the sorted array. If the number at that position is this number, then the difference is 0, it is the lowest possible one, so I exit the loop. Else, I insert the number in the sorted array at that point, then check the difference between that number and the previous and next numbers in that array. Then I store the minimum of this result and the previous result, and continue in this fashion.</p> <p><strong>Second: I sort the array using quicksort</strong>. (The range is too large, so I think radix sort won't be that efficient). Then I iterate over it, breaking out with an answer of 0 if two consecutive numbers are equal, else storing the minimum of the difference between that number and the previous number and the previous result.</p> <p><strong>Which one will be more efficient?</strong></p> <p><strong>Is there any better algo?</strong> </p> <p>Stackoverflow has a number of posts in this regard, but they didn't help much. Here's my code in Perl:</p> <pre><code>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"; </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload