Find nearest number in unordered array

Question

Given a large unordered array of long random numbers and a target long, what's the most efficient algorithm for finding the closest number?

@Test
public void findNearest() throws Exception {
    final long[] numbers = {90L, 10L, 30L, 50L, 70L};
    Assert.assertEquals("nearest", 10L, findNearest(numbers, 12L));
}

Answer 1

Iterate through the array of longs once. Store the current closest number and the distance to that number. Continue checking each number if it is closer, and just replace the current closest number when you encounter a closer number.

This gets you best performance of O(n).

Building a binary tree as suggested by other answerer will take O(nlogn). Of course future search will only take O(logn)...so it may be worth it if you do a lot of searches.

If you are pro, you can parallelize this with openmp or thread library, but I am guessing that is out of the scope of your question.