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

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.

• When the distance to both the larger and the smaller value is the same, which one has precedence? – le_m Dec 22 '17 at 20:43
• Also, shouldn't getClosest(true, false, 99).value be 90 instead of 110? The distance to 90 is 9 which is "smaller/equal than [the] given delta". – le_m Dec 22 '17 at 20:46
• I re-read problem definition a dozen of times and still don't understand how default, next, and offset should work together. – Igor Soloydenko Dec 22 '17 at 21:35

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.

• Very good review. Having the boolean "flag" parameters is definitely a smell/bad practice and should be avoided. Also, +1 on the binary-search based approach too! Have a question on null === shortest. Is it really JS-idiomatic? Could you point me to popular JS libs that follow that? I have seen this in C/C++ but not in JS, and it actually a very arguable practice because this is not the way we read English text. – Igor Soloydenko Dec 22 '17 at 23:02
• @IgorSoloydenko I've seen the null === shortest literal-first recommendation in PHP, but not in JS. The reason given was that assignment to a literal throws a parse error. In JS, we could only expect a runtime error which is less useful, but still better than silent assignment without warning. I wouldn't consider it idiomatic. I don't like it for the same reason you stated, it's just more difficult to read. – le_m Dec 22 '17 at 23:12
• Some clarifications: Only the method/function getClosest (and its signature/interface/parameters) should be part of the review. The original object is highly customizable where this.values, this.delta etc. are all set during construction. That's the part I simplified to make the question focus on the actual method. I'm sorry, that this wasn't clearly worded. – lampshade Dec 27 '17 at 11:34
• What helped me most: Less than 4 values: Good catch, that this fails. find-prefix: Very good point. Variable names: Those are very, very good points as well - will fix them all. Signature: Good point too. Due to some refactoring of the class the value-paramater was added later. Will move it to the pole position. Splitting the function: That is a good point too in regard of single responsibility. I'm considering splitting that method up now. – lampshade Dec 27 '17 at 11:36
• What I don't see as a problem: Yoda condition: I don't think that this is a bad thing and one can discuss the readability of it. But you're right by saying indirectly to stick to one style and don't mix it. So I will change that as well. – lampshade Dec 27 '17 at 11:37

## 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.

• Thank you very much for your review, too. This looks like something I had in mind while writing the question. The three loops and the repition where my main concerns. The exit strategy looks promising as well. Again, thank you very much for your help. – lampshade Dec 27 '17 at 11:40