Given a number: find the closest value in a list of unique and sorted numbers with some twists

Question

I have a method getClosest() in an object, that does the following:

Given a number: Find the closest number in a list of unique and sorted numeric values.

On top of that it has two additional ptions next|offset:

• default: find the closest value, smaller or larger than the submitted value
• next: find the next value in the list, that is larger than the submitted one
• offset: like default but find the smaller value only, if the distance to it is smaller/equal than a given delta

---

You can also assume that:

• the input value will always be smaller then or equal to the largest value in the set
• all parameters have the correct type (integer|boolean)
• the list will contain between 10-20 values

---

This is an example of the list:

this.values = [0, 35, 90, 110, 160, 175, 200];

The function returns an object, holding the position as well as the actual value:

{
    index: 1,
    value: 35
}

---

class Test {
  constructor() {
    this.values = [0, 35, 90, 110, 160, 175, 200];
    this.delta = 12;
  }

  getClosest(offset, next, value) {
    let closest,
        comparativeValue;

    if (offset === true) {
      for (let i = 0; i < this.values.length; ++i) {
        const current = this.values[i];

        if (value <= current) {
          closest = {
            index: i,
            value: current
          };
          break;
        }

        if (value > current) {
          comparativeValue = {
            index: i,
            value: current
          };
        }
      }

      if (comparativeValue) {
        const offsetA = Math.abs(closest.value - value);
        const offsetB = Math.abs(comparativeValue.value - value);

        if (this.delta < offsetA && this.delta > offsetB) {
          return comparativeValue;
        }
      }
    }

    if (next === true) {
      for (let i = 0; i < this.values.length; ++i) {
        const current = this.values[i];

        if (current > value) {
          closest = {
            index: i,
            value: current
          };
          break;
        }
      }
    }

    if (!offset && !next) {
      for (let i = 0, shortest = null; i < this.values.length; ++i) {
        const current = this.values[i];
        const delta = Math.abs(current - value);

        if (null === shortest || shortest > delta) {
          closest = {
            index: i,
            value: current
          };
          shortest = delta;
        }
      }
    }
    return closest;
  }
}

const test = new Test();

console.log(
  test.getClosest(false, false, 10).value,
  test.getClosest(false, false, 100).value,

  test.getClosest(false, true, 10).value,
  test.getClosest(false, true, 100).value,

  test.getClosest(true, false, 10).value,
  test.getClosest(true, false, 100).value,
);

---

My concerns are:

• overcomplicated
• this ain't DRY at all
• too many loops and variable declarations
• there's a call getClosest(true, true, 40), which might lead to unexpected results

---

You can ignore the Test-object-wrapper. It's to simplify the example and to make the code easily runnable. Here's a fiddle as well to play around with.

Answer 1

The given specification is incomplete and your implementation differs from the specification.

• For example, according to your specification, test.getClosest(true, false, 99).value should be 90 instead of 110, since the distance from 99 to the closest value 90 is 9 which is "smaller/equal than [the] given delta" of 12.

Also, it is not clear how strong the given assumptions are and whether or not violations of those assumptions can occur and should be dealt with.

• For example, your implementation fails on lists of less than 4 values. Now, one could say that this isn't a problem due to the assumption that a "list will contain between 10-20 values". But it is generally considered bad practice and a more robust implementation would be recommended.

In addition to that, we don't know which parts of your interface or method signature are given and which parts are subject to review. You write that we "can ignore the Test-object-wrapper". But what about the method signature with its unorthodox choice of arguments, which seems to be required by the given specification?

For all these reasons, it is hard to provide a meaningful review.

Some notes:

1. getClosest(offset, next, value)

   • the get prefix usually indicates a lookup or simple computation. If more complex computations are required instead, I prefer using another verb such as findClosest.
   • Also, I recommend renaming offset to something more appropriate - it clearly isn't an offset.
   • Most developers would probably expect the value as the first argument, similar to built-in functions such as parseInt(string, radix) or Array.prototype.includes(value, offset).

2. if (null === shortest || shortest > delta) { ... }

   • putting the literal value on the left side of the comparison operator helps to detect some typos early on, when one accidentally uses the assignment operator = instead of the comparison operator == or === within a comparison expression. However, this also makes the comparison more difficult to read. I prefer the other way around.

3. const offsetA = Math.abs(closest.value - value)

   • this is actually a delta and not an offset. I suggest const deltaNext or similar.

4. let closest, comparativeValue

   • closest is not necessarily the closest value. It is the next larger value.
   • Also, consistency would demand either attaching the redundant Value suffix to both identifiers or none.
   • Putting each variable declaration on its own line improves readability, but I also prefer giving each declaration its own let as this simplifies modifications in the future.

5. if (offset === true) { ... }

   • instead of strict comparison, I'd simply check for a truthy value via if (offset) { ... }. This duck typing approach fits better with the language. You already use it when writing if (!offset && !next) { ... } or if (comparativeValue) { ... }.

6. shortest = delta

   • now you have closest (which is actually the next larger value), comparativeValue, shortest (which is actually the minimum delta), delta, this.delta, offset (which is actually a boolean flag) etc. It is hard to follow your naming scheme. I suggest more descriptive and more consistent naming.
   • Also, I wouldn't declare both an instance property this.delta and a local variable delta with different semantics.

Further suggestions:

1. It is not obvious to me why the arguments this.values and this.delta are given as instance properties and defined within the constructor function. By doing so, you create a stateful object which is more difficult to understand and test than e.g. a simple 'pure' function.

2. Also, by setting the next flag, the semantics of your method are no longer compatible to the meaning of getClosest. How about two methods findClosestEntry and findCeilingEntry? The Entry suffix indicates that the return value is a complex object containing index and value, comparable to e.g. Array.prototype.entries or Object.entries. Those established methods iterate or return [index, value] arrays instead of {index, value} objects, so you might want to consider following this established pattern, too.

3. Instead of passing an offset flag and relying on instance properties this.delta and this.values I suggest a method signature such as findClosestEntry(array, element, delta) and passing (or not passing) a delta argument.

4. I would replace the many for-loops with a single const nextIndex = values.findIndex(element => element > value). You would then have to lookup const prevValue = values[nextIndex - 1] and const nextValue = values[nextIndex] and return either one depending on the given flags. Don't forget to test for the corner case when nextIndex === -1 and consider handling it appropriately.

5. If you had to handle more than 20 values, I'd implement a binary search and - if the number of queries for a given array of values is large, built a binary search tree first. This would improve runtime complexity from linear to logarithmic. But for just up to 20 values, the built-in Array.prototype.findIndex or even an explicit for-loop is surely faster.

Answer 2

Solve all at once.

This is 3 problems in one but they all share some similarities. There is no clear cut way to effectively separate the 3 functions without some code repetition. The best option would be to solve all 3 at once and just return the appropriate result.

You are looking for two values, the closest value below and the closest above. If you search from the lowest up, you can exit the search as sone has you get to the first value above searched for value. This will on average reduce the iteration by ~half (depending on the distribution and number of items).

Because the array is already sorted the search is very simple. Get the dif between the submitted value and array value. Each value less than 0 must be the closest so far (as array values are increasing)

As soon as the dif is greater than 0 you have found all the data needed to answer any of the 3 types of data. Exit the loop and then check what needs to be returned.

const setup = (values, delta) => {
    return (offset, next, value) => {
        var lowDist, highDist, lowVal, highVal, i  = 0;
        while (i < values.length) {
            const currentVal = values[i++];
            const dif = currentVal- value;
            if (dif < 0) { 
                lowVal = currentVal; 
                lowDist = dif;
            } else { 
                highVal = currentVal; 
                highDist = dif;
                break;
            }
        }
        if (offset) {
            if (lowDist <= -delta) { return lowVal }
            return undefined;
        }
        if (next) { return highVal }
        if (-lowDist < highDist) { return lowVal }
        return highVal;
    }
}

// setup the data and get the search function
const getClosest = setup([0, 35, 90, 110, 160, 175, 200], 12);

// do the search and output the result.
console.log(getClosest(false, false, randomValue));

You could get an earlier exit for the offset option by adding if (dif < -delta) { break } below the line lowDist = dif but on average this increases the amount of work so best to keep it as simple as possible.