Take the 2-minute tour ×

There is an array which can contain, say, upto 1000 elements. The range of numbers it can spawn is say 1 to 10^10. Now I have to find the minimal absolute difference between two numbers in the array. I have thought of two algorithms:

For the first one, I have defined a binarysearch 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.

Second: I sort the array using quicksort. (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.

Which one will be more efficient?

Is there any better algo?

Stackoverflow has a number of posts in this regard, but they didn't help much. Here's my code in 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;
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;
    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";
share|improve this question
Is it going to happen very often? Otherwise, 1000 elements is really not a big deal - and is most likely does not deserve your time optimizing it –  amit Sep 2 '12 at 6:46
It can contain upto around 5000 elements. –  Cupidvogel Sep 2 '12 at 6:47
Still very small. Unless it happens very often, no optimization is going to worth your time –  amit Sep 2 '12 at 6:49
To understand how small it is: sandy-bridge processor has 32KB L1-Cache. Assuming 4 bytes integer, it can support up to 8192 integers. If you really want to optimize the solution - focus on solutions that are as cache friendly as possible, and avoid creating more data as much as possible. in place quicksort will probably outperform any other solution –  amit Sep 2 '12 at 6:51
Please use pragma use strict;, it helps you! –  Pavel Vlasov Sep 2 '12 at 7:05

7 Answers 7

up vote 13 down vote accepted

You have up to 5k elements.

Note that a sandy bridge processor has 32KB L1-Cache, assuming 4 bytes integer - it means it can contain 8192 integers.

I'd try to avoid as much as possible creating additional data (except counters and such), and do everything in place using the same array. This will make the number of cache-misses very small, and will probably outpeform any algorithm.

Thus, an in-place quicksort and than iterating over the elements in the array will probably be better then any other solution, both for being cache-efficient, while still keeping decent asymptotical complexity of O(nlogn).

Note - Although this solution will probably be more efficient (at least theoretically), the scale is still very small - and unless you are going to do this oporation a lot of times - it just doesn't worth your time over-optimizing it.

General tip: when talking about small scale problems (and up to 5000 elements fits this criteria) the big-O notation is usually not enough. The cache performance is usually the dominant factor in these problems.

share|improve this answer
Assuming 4 bytes for an integer is kind of silly when you know that the problem is in Perl, isn't it? For reference, an SVIV is going to be 16 bytes on a 32-bit system and 24 bytes on a 64-bit system; and the AvARRAY overhead is another 4 bytes each on 32-bit and 8 bytes each on 64-bit, for a total storage requirement of 20*n bytes (plus change) on 32-bit and 32*n bytes (plus change) on 64-bit. –  hobbs Sep 2 '12 at 7:18
@hobbs: Thanks for commenting. I focused mainly on the theoretical aspects of such a problem (focusing more on the algorithm tag then the pearl one). Nevertheless, even if the exact numbers are not correct for pearl, it is still something to be considered. If the data does not fit L1 because of pearl's overhead - you should do whatever you can in order to make it fit the L2 cache. –  amit Sep 2 '12 at 7:22
This processor stuff and their effect on algorithms is entirely new to me. Can you elaborate a bit further, or better, point me to an article which does so? –  Cupidvogel Sep 2 '12 at 8:01
So reading from cache is better than reading from RAM, just as reading from RAM is better than reading from storage? Then this is a generic improvement, how does it concern our problem? –  Cupidvogel Sep 2 '12 at 8:09
Assuming 4 bytes integers also seems kind of silly when the problem specification says between 1 and 10^10. –  Mark Byers Sep 2 '12 at 8:43

This is the closest pair problem in one-dimension. Note that solving this problem is at least as hard as solving the element uniqueness problem, since if there are any duplicate elements then the answer is 0.

The element uniqueness problem requires O(n lg n) time to solve, so this problem must also be at least that hard. Since the sort-the-iterate solution you proposed is O(n lg n), there is no better asymptotic worst-case algorithm available.

As noted in the wiki article however, there are algorithms that have worse worst-case running time, but linear expected running time. One such method is described in this article, it seems pretty complicated!

share|improve this answer
Using hash tables you can get average O(n) time for element uniqueness –  amit Sep 2 '12 at 7:18
For element uniqueness, won't the binary search algorithm provide better performance (O(log N))? –  Cupidvogel Sep 2 '12 at 7:22
@Cupidvogel Yes, the search is O(lg n), however, insertion of an element into an arbitrary position in an array is O(n), since you have to move all the following elements. If you switch to some other data structure that has both O(lg n) search and O(lg n) insertion (I don't know one of the top of my head) then the whole process would still be O(n lg n), which is the same as the sort-and-iterate method. –  verdesmarald Sep 2 '12 at 8:38
“The element uniqueness problem requires O(n lg n) time to solve”—be careful with such statements. OP said the input is a list of bounded integers, and it is known that in such case you can sort them faster than O(n log n) (see Wikipedia), which also makes element uniqueness problem on such data faster. –  liori Sep 2 '12 at 16:07
@liori The question doesn't say integers, it says numbers, but reading the comments it seems the OP did mean integers, so fair point. For this question, however, a non-comparative sort doesn't buy you anything, even for extremely large n. If a list of integers is bounded by (0, 2^k), the list can be sorted in O(kn). Note, however, that if n < 2^k, lg n < k, so in practice non-comparative sorts are only faster when n > 2^k (give or take). The kicker here though, is that n > 2^k gives us the answer 0 immediately, since there must be a duplicate (by the pidgin-hole principle). –  verdesmarald Sep 3 '12 at 0:16

The second one will be faster for the very simple reason that with the first solution you're using a sort that you wrote yourself in Perl-space, while with the second solution you have the opportunity to use the Perl built-in sort which is a C function and very fast. With such a small input, it will be nearly impossible for the first one to win, even though it has the potential of doing less work.

share|improve this answer
Why would the Perl built in sort function function faster because it is written in C? Does it mean that if I write a Perl sort function exactly similar to the native sort, it will perform slower in comparison? –  Cupidvogel Sep 2 '12 at 7:22
@Cupidvogel definitely — just try it! –  hobbs Sep 2 '12 at 7:24
Why does this happen? Is this because C needs strong typing, due to which element type finding is eliminated at compile time? –  Cupidvogel Sep 2 '12 at 7:25
@Cupidvogel that's a small part of the reason. The C sort will have less overhead than the Perl version in a lot of ways. It will use less storage and be more cache-friendly because of native types; it will do less work because of native type semantics (no checking array bounds, no promoting integers to floats, no ref-counting, and as you say, no need to check at runtime what the type of a variable is), and it will have less control-flow overhead due to being native compiled code and not perl opcodes. –  hobbs Sep 2 '12 at 7:36
What exactly do you and @Amit mean by caching? What is being cached here? I thought caching is important in DB data lookups, where caching can bring the data from memory instead of storage, thus reducing costly I/O operations. –  Cupidvogel Sep 2 '12 at 8:01

Second algorithm is probably better. In the first algorithm, you are using insertion sort, which is less efficient than some other sorting algorithms.

share|improve this answer

A simple randomized sieve algorithm for the closest-pair problem describes an O(n) randomized algorithm for the closest pair problem and it also references another paper which gives an O(n log log n) deterministic algorithm for the one-dimensional closest-pair problem if you have access to the floor function.

share|improve this answer

Because we are talking Perl, we should not wonder to much about the most efficient sorting algorithm — implementing something yourself in Perl is bound to be slower than using built-ins. Just for fun, I ran this little script (intendated for clarity):

time perl -e'
    @array = map {rand} 1..100000;
    for(sort {$a <=> $b} @array){
        unless(defined $last){
        $difference = abs($last - $_);
        $last = $_;
        $lastdiff = $lastdiff < $difference ? $lastdiff : $difference;
        last if $lastdiff == 0;
    print $lastdiff, "\n"

I set up an array with 100,000 random numbers. This script terminates (on my slow laptop) inside 0.42 seconds. Considering I use ~0.12 seconds for startup and array initialization, the main algorithm uses circa 0.3 seconds. Assuming O(n) you should finish in < 0.02 sec … oh, wait, that isn't much… (with 5000 elems)

If you need it faster, write your algorithm with Inline::C.

share|improve this answer
@Cupidvogel What exactly do you mean with "this happen[ing]"?Perl gives you flexibility at the price of performance — Perl doesn't even compile to machine code, so each operation has a high overhead. Number chrunching with Perl is a bit like chopping trees with a pen knife. –  amon Sep 2 '12 at 7:29
  1. copy numbers of array into black-red tree
  2. this would allow you testing if there is a number in certain interval for log(n)
  3. set d = inf
  4. loop over array with variable i
  5. if there is a number in interval (i-d, i+d), then set d equal to |i-thatNumber|

it'd take you ~ n*ln to find d

share|improve this answer
I hardly doubt inserting elements into a non cache-efficient tree will do better then a quicksort and a single iteration. Both are O(nlogn), but the second (quicksort+iteration) will most likely have much better constants –  amit Sep 2 '12 at 6:45
That seems overly complicated. Sorting the array and then iterating it once also finds the answer in O(n lg n) time. –  verdesmarald Sep 2 '12 at 6:45
The first one can immediately find whether tow numbers are same and exit. The sorting will sort it anyways, and if the two number which are same are pretty large so that they re towards the end of the array, the iteration will take much time. –  Cupidvogel Sep 2 '12 at 6:46
@Cupidvogel Iterating the array is practically free compared to the cost of sorting it. –  verdesmarald Sep 2 '12 at 6:55

Your Answer


