Find the nearest number in an unordered array

Question

Given the large random array of long random numbers and the target long, what is 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 an array of long times. Save the current nearest number and the distance to this number. Keep checking each number if it is closer, and simply replace the current nearest number when you find a closer number.

This gives you better O (n) performance.

Building a binary tree, as suggested by another responder, will accept O (nlogn). Of course, future searches will only accept O (logn) ... so this may be worth it if you are doing a lot of queries.

If you're a pro, you can parallelize this using the openmp library or stream, but I assume this is beyond the scope of your question.

Answer 2

If you are not going to execute several such queries in an array, there is no better way than checking the brute force linear time for each number.

If you make multiple queries in one array, first do a sort and then do a double search - this will reduce the time for such queries to O (log (n)), but you still pay O (n * log (n)) to sort , therefore it is reasonable if the number of requests is large enough, i.e. k * n → (much more) n * log (n) + k * log (n), where k is the number of requests.

If the array changes, create a binary search tree tree and run a query with a lower bound. This is again reasonable if the request for the nearest number is relatively large compared to requests for changing the array, as well as the number of elements. Since the cost of building the tree is O (n * log (n)), as well as the cost of updating is O (logn), you need to have k * log (n) + n * log (n) + k * log (n) < (much less) k * n

Answer 3

IMHO, I think you should use a Binary Heap (http://en.wikipedia.org/wiki/Binary_heap) which has an O (log n) insertion time that is O (n log n) for the whole array. For me, the coolest thing in the binary heap is that it can be done internally from your own array without the overhead. See the heapfy section.

"Heapfying" your array allows you to get a higher / lower element in O (1).

Answer 4

if you create a binary search tree from your numbers and do a search. O (log n) will be the worst case complexity. In your case, you will not look for equality instead, you will look for the smallest return value through subtraction

Answer 5

I would check the difference between the numbers during iteration over the array and save the min value for this difference.

If you plan to use findNearest several times, I would calculate the difference in sorting (with the n * log (n) complexity sorting algorithm) after each change in the values ​​in this array

Answer 6

The time complex for this task is O (n), the length of the numbers.

  final long[] numbers = {90L, 10L, 30L, 50L, 70L}; long tofind = 12L; long delta = Long.MAX_VALUE; int index = -1; int i = 0; while(i < numbers.length){ Long tmp = Math.abs(tofind - numbers[i]); if(tmp < delta){ delta = tmp; index = i; } i++; } System.out.println(numbers[index]); //if index is not -1 

But , if you want to find many times with different values, such as 12L versus one array of numbers, you can sort the array and binary search first by the array of sorted numbers.

Answer 7

If your search is one-time, you can split the array, as in quicksort, using the input value as a pivot point.

If you save the track - when splitting - of the min element in the right half and the maximum element in the left half, you should have it in O (n) and 1 single pass through the array.

I would say that it is impossible to do less than O (n), since it is not sorted, and you need to scan the input at least.

If you need to do a lot of subsequent searches, then BST can really help.

Answer 8

You can do it below.

Step 1 : Sort Array

Step 2 : find the index of the search item

Step 3 Based on the index, display the number on the right and left.

Let me know about any inquiries ...