Always check upper and lower bounds

This is part of the Semicolon&Sons Code Diary - consisting of lessons learned on the job. You're in the algorithms category.

Last Updated: 2021-05-15

I wrote the following code:

export function findNextHighestKey(object, bound) {
  const sortedKeys = Object.keys(object).sort((a, b) => Number(a) > Number(b))

  for (let i = 0; i < sortedKeys.length; i++) {
    if (sortedKeys[i] >= bound) {
      return sortedKeys[i]
    }
  }

  const defaultIfNoneFound = 0
  return sortedKeys[defaultIfNoneFound]
}

As depicted below, I tested the lower bounds and the middle bounds and concluded it worked fine:

object = {"10": "a", "25": "b"}
findNextHighestKey(object, 9)
=> "10"

findNextHighestKey(object, 12)
=> "10"

findNextHighestKey(object, 11)
=> "25"

However, as you'll see here, I did not test the upper bound. And it was only much later that I noticed the function failing in this case:

findNextHighestKey(object, 27)
=> "10" // should be 25

What really should have come out was 25, the top key.

Here is the fixed code:

function findNextHighestKey(object, bound) {
  const sortedKeys = Object.keys(object).sort((a, b) => Number(a) > Number(b))

  for (let i = 0; i < sortedKeys.length; i++) {
    if (sortedKeys[i] >= bound) {
      return sortedKeys[i]
    }
  }

  // Handle special cases where no key was larger than the bound
  const smallestKey = sortedKeys[0]
  const biggestKey = sortedKeys[sortedKeys.length - 1]
  if (bound <= smallestKey) {
    return smallestKey
  } else {
    return biggestKey
  }
}

Lessons:

Always check at least these three conditions for correctness in functions of orderings.