Efficient way of comparing value in array to all values before in array

Question

I have a very long array numbers[]. My algorithm needs to find the lowest index j in numbers[] at which the |numbers[j] - numbers[i]| <= x(a random variable) or where |numbers[j] - numbers[i]| >= m - x (m another variable, larger than x) and where i<j.

This is my algorithm now:

 for (int j = 1; j < numbers.Length; j++)
 {
     for (int i = 0; i < j; i++)
     {
        long diff = Math.Abs(numbers[j] - numbers[i]); 
        if (diff <= x || diff >= m - x)
            return j;
     }
 }

Can this be done more efficiently? An input with very high numbers, for instance, takes my laptop about 36 seconds.

Is there an upper limit on the numbers and the x, other than the implied limit of Int32.MaxValue? — Sergey Kalinichenko
– Sergey Kalinichenko, Commented May 17, 2015 at 20:31
the largest x can be is 10 million, the other values ( in the array) can be up to 100 billion. — user1760791
– user1760791, Commented May 17, 2015 at 20:32
Just by curiosity, what is the purpose of the algorithm? What do you do with the j index? Why not returning i as well? — Kryptos
– Kryptos, Commented May 17, 2015 at 20:43

Peter de Rivaz · Accepted Answer · 2015-05-17 20:33:28Z

1

You could do this in O(nlogn) by iterating through the array and at each stage adding the new number to a balanced search tree.

When you add the number you first search for the closest number already in the search tree. If this number is less than the target difference then you have found the answer.

answered May 17, 2015 at 20:33

Peter de Rivaz

33.6k4 gold badges51 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Peter de Rivaz Over a year ago

A balanced search tree is a bit too much code to add to the answer, but I've found a plausible implementation here

Collectives™ on Stack Overflow

Efficient way of comparing value in array to all values before in array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related