2020-08-13

The Closest Prior: A conversation#

So recently Hrishi came up to me and asked how I'd write a sort function that would, given a number x, sort a list such that the first item would be the one closest to, but smaller than, x. He wanted to use this in a function to get the closest prior from a list. Basically:

var ls = [3, 6, 2, 1, 7, 3, 5, 9];
get_closest_prior(8, ls) >> 7;
get_closest_prior(5, ls) >> 5;

The conversation went something like this.

Me:Why don't you just iterate?

Him:I don't want to iterate, sorting's generally faster with less comparisons. Because inbuilt functions.

Me:Fair, but how are you sorting?

Him:That's what I'm asking you.

Me:Uhhh... give me a sec.

So in my mind there's two parts to this. You want all numbers greater than x to be at the end of the list. Then, at the front of the list, you want all numbers smaller than x to be sorted in reverse order. Basically, given a sorted list with x in the middle:

← smallest

biggest →

^{^}

You want to sort the list something like this:

I gave him this sorting function, with an appropriate try/catch block to handle divide by zero errors. Using try/catch means that the additional comparisons (ie whether a or b is equal to x) are only performed when necessary, instead of every time.

function sort_closest_prior(x, a, b) {
    if (1 / (a - x) > 1 / (b - x)) {
        return 1;
    } else {
        return -1;
    }
}

This sort function is basically normal sort, on a transformed array. Each array element e is transformed by $\frac{1}{e-x}$ . Subtracting x recenters the array so that x = zero,

← negative

positive →

^{^}

and then dividing by that inverts the magnitude of each number, to leave the closest prior as the smallest item in the transformed array.

negative →

← positive

^{^}

Me:Here you are!

Him:Ahhh. I guess I'll just iterate over it.

Me:Huh? You wanted a sort function and this works.

Him:It's got a divide.

Me:Yes it does.

Him:I don't like floating points. They're unpredictable and make debugging painful, I was hoping there'd be a way using just subtraction and abs .

Me:Like abs(e-x) ?

Him:Yup, but that gives just the closest number to x , not the closest number less than x .

Me:What's your plan if x is smaller than every element in the array?

Him:Just return None .

Me:...why not just filter out all elements greater than x , then sort descending?

And that's one story of how easy it is to complicate something far beyond necessity.