How to find the closest double in an unsorted array

Question

I have a set of points in discrete space, and the coordinates are given as N double [] arrays.

For instance:

Point T1 = {1.3,2.5,4-3} ---> double [] x = {1.3}, double [] y = {2.5}, double [] z = {4.3}

Then I have a function that generates an offset from a given point in all directions in continuous space, and I need to find the closest match in my matrix / double array.

The problem is that I cannot sort these arrays and apply a binary search, because Point components most likely will not have the same indexes after sorting relative to each other.

Is there some kind of data structure / algorithm that I could apply to avoid iteratively searching for the closest match point?

Would it be better to arrange the points so that there is one instance of the array describing the whole point, and not an array per component?

Edit

It seems that the ideal solution would be to use kd trees as indicated in the comment. Computer algorithms are not my domain, so an answer showing a minimal example with kd trees, or some alternatives, will be most useful when I explore the topic.

Answer 1

If I understand your problem, you have N arrays of size M floats, each of which contains the coordinate of a point along an axis in N-dimensional space. You also have one float, and you want to find the index of the point for which the float is closest to one of the components. If this were correct, I would create a single array whose elements are pairs (value, index), and the value is one of the components, and the index is the index of the point to which the component belongs. Then you can sort the array using the value as sorting.key. at this point you can use binary search using float.

Of course, creating and sorting an array makes sense only if you have several floats to search for, since sorting will take O (K log K), with K = N * M, and searching after that will take O (log K). If you only need to search for one float, you can also do a full search on the array, which will be O (K).