The question is to find the 2 closest elements, lets look at an example:
What would be the two closest elements in this list?
data = {1,45,32,7,87,54,10};
Hmm, its hard to tell by looking.
One thing we could do would be to compare each element, with every other element, something like this:
for(int a = 0; a < data.length; a++) {
for(int b = 0; b < data.length; b++) {
//compare data[a] to data[b], keep track of closest
}
}
This is called a brute force approach, and would result would be O(n^2)
solution, which is too slow for your purposes.
Lets try a different approach; lets try sorting the array first.
data = {1,45,32,7,87,54,10};
sorted = magicalSort(data) //You will have to implement the sorting
The contents of sorted are as follows:
{1,7,10,32,45,54,87}
By sorting the data first, finding the closest 2 elements becomes a lot easier, it doesn't take long to look and see that 7
and 10
are the closest two.
The cost of this solution would be :
O(n log n)
for sorting (see Quicksort and Mergesort), plus O(n)
for iterating over the sorted list and searching for the closest two elements.
This gives you:
O(n log n) + O(n)
which is approximately:
O(n log n)
.