Find a number nearest to all numbers in an array

4
votes

This problem is basically an algorithm optimization problem.

We have a list which has n elements. for e.g. {n1,n2,n3...nk} This list is sorted and we have to find out the number ni which is

  1. n1<=ni<=nk
  2. The sum of distance of ni from each number is minimum.

There may be total (nk-n1+1) possible numbers but our objective is to find out the number ni which is nearest to all other numbers.

Brute force approach could be iterate through n1 to nk and calculate the sum of distance from all list numbers. This way easily we can figure out the number who is closest to all other numbers in the list.

But the problem with this approach is, it is not good in terms of time complexity. The time complexity of this approach is O(n^2).

I think there could be better method to do this which can solve this problem with less time complexity.

Any approach will be appreciated.

3
arraysalgorithmoptimizationnumbers
What definition of "distance" do you use? – Klas Lindbäck
How about searching with binary search cos you mentioned that list is sorted? – kamaci
yes distance(a,b)=abs(a-b) – vicky

3 Answers

6
votes

If by "distance" you mean distance(a,b) = abs(a-b) then you simply need to find the median.

Finding the median in a sorted list is O(1).

1
votes

The answer should be ROUND( SUM(n1,...,nk)/k ) .

0
votes

Find the average ... this takes O(n). Then walk through the list to find ni for the average (also takes O(n))... actually more like o(1/2n)