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:

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,

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

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.