DEV Community

Discussion on: Challenge: Get Closest Number in an Array

Collapse
 
lucifer1004 profile image
Gabriel Wu • Edited

And there is another perspective, instead of iterating numbers, we can iterate distances. Like:

const closest_num = (nums, given_num) => {
  const set = new Set(nums)
  let i = 0
  while (true) {
    if (set.has(given_num - i)) return given_num - i
    if (set.has(given_num + i)) return given_num + i
    i++
  }
}

This will normally be slower, but in cases like:

nums = [10000000, 9999999, 9999998, ..., 1]
given_num = 10000001

It will be much faster than other algorithms.

I have written a benchmark function for this:

const benchmark = (func) => {
  console.time(func.name)
  func.call(this, Array.from({length: 10000000}, (v, idx) => (10000000 - idx)), 10000001)
  console.timeEnd(func.name)
}

You can test your function via benchmark(func).

The solution above yields:

closest_num: 5037.456787109375ms

in Chrome.