Searching through an unsorted nonuniform pair array for closest entry

Question

I have an array that looks something like this:

[[320, 80], [300, 70], [300, 80], [270, 75], [260, 70], [280, 70]]

That is just a snippet, the actual array is 338 big.

I am trying to find the next logical element in the array based on some input. So for example I feed in two numbers, I.e. 315, 80 The next logical one is 320, 80 if you wanted to find a bigger entry.

I don't want to correlate logical to closest because it depends on whether you want a bigger or smaller element. So I suppose by logical I mean "closest in the required direction"

As an additional requirement the second number should try and remain as close as possible to the entered value OR the first number should try and remain as close as possible to the original number.

I am having issues when it comes to cases such as 275, 70, and I want to find the next smallest. That should be 260, 70 but my implementation keeps picking 280, 70

My current implementation adds the difference between the two numbers and looks for the smallest difference possible. I'm not sure how to enforce a direction.

Python Example (although really I'm looking for a language agnostic solution)

elements = [ [320, 80],
             [300, 70],
             [300, 80],
             [270, 75],
             [260, 70],
             [280, 70]
           ]

target = [275, 70]
bestMatch = []
bestDifference = 0

for e in elements:
    currentDifference = abs((target[0] - e[0]) - (target[1] - e[1]))

    if not bestMatch or currentDifference < bestDifference:
        bestMatch = e
        bestDifference = currentDifference

print bestMatch

Answer 1

Based on your description and example input I have interpreted that as you should take the min of the two differences, rather than the difference of them. Then you'll pick the element that has the smallest change in either of the two numbers.

To go in the right direction you can just check whether the element you are currently at is larger or smaller than the target

Doing that you'll get the following:

elements = [ [320, 80],
             [300, 70],
             [300, 80],
             [270, 75],
             [260, 70],
             [280, 70]
           ]

def nextLogicalElement(target, bigger=True):
    bestScore = 0
    bestMatch = []
    for e in elements:
        score = min(abs(target[0] - e[0]), abs(target[1] - e[1]))

        if bigger and target[0] > e[0] or not bigger and target[0] < e[0]:
            continue

        if not bestMatch or score < bestScore:
            bestMatch = e
            bestScore = score

    return bestMatch

Output:

>>> print nextLogicalElement([315, 80], bigger=True)
[320, 80]
>>> print nextLogicalElement([275, 70], bigger=False)
[260, 70]