1
\$\begingroup\$

For my project I have a sorted array of objects of timestamps (in milliseconds) and I need two functions. One function should find the closest time that doesn't go over a specific amount, and the other function should find the closest time that doesn't go under a specific amount. Also, they should return the indices of values.

For example, if I have this data:

let a = [ { t: 50 }, { t: 100 }, { t: 400 }, { t: 800 }, { t: 850 } ];

Then closestUnder(arr, 375) should return the index for { t: 100 }, which would be 1

And closestOver(arr, 450) would return the index for { t: 800 }, which is 3

function binarySearchNearest(a, value) {
  if (value < a[0].t) { return 0; }
  if (value > a[a.length - 1].t) { return a.length - 1; }

  let lo = 0;
  let hi = a.length - 1;

  while (lo <= hi) {
    let mid = Math.floor((hi + lo) / 2);

    if (value < a[mid].t) {
      hi = mid - 1;
    } else if (value > a[mid].t) {
      lo = mid + 1;
    } else {
      return mid;
    }
  }

  return a[lo].t - value < value - a[hi].t ? lo : hi;
}

function closestOver(arr, value) {
  let i = binarySearchNearest(arr, value);
  
  let entryIndex = arr[i].t < value && i + 1 < arr.length ? i + 1 : i;

  return arr[entryIndex].t >= value ? entryIndex : -1; 
}

function closestUnder(arr, value) {
  let i = binarySearchNearest(arr, value);

  let entryIndex = arr[i].t > value && i - 1 >= 0 ? i - 1 : i;

  return arr[entryIndex].t <= value ? entryIndex : -1; 
}

let a = [ { t: 50 }, { t: 100 }, { t: 400 }, { t: 800 }, { t: 850 } ];

console.log(closestUnder(a, 375));
console.log(closestOver(a, 450));

\$\endgroup\$
1
\$\begingroup\$

Simplify the logic

The simplest form of binary search function returns the index where the target value would be inserted to keep the list sorted. This would imply that:

  • When an exact match exists in the list, its index is returned
  • Otherwise the index of the next higher element is returned
  • If there is no next higher element, the length of the list is returned

This last point is the most important caveat to watch out for: before using the returned index on the list, you must check that it's less than the length.

The implementation of this more classic form is simpler than binarySearchNearest.

function binarySearch(arr, value) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((hi + lo) / 2);

    if (value < arr[mid].t) {
      hi = mid - 1;
    } else if (value > arr[mid].t) {
      lo = mid + 1;
    } else {
      return mid;
    }
  }

  return lo;
}

Based on this simpler logic, the other functions become simpler too:

function closestOver(arr, value) {
  const index = binarySearch(arr, value);
  return index == arr.length ? -1 : index;
}

function closestUnder(arr, value) {
  const index = binarySearch(arr, value);
  return index < arr.length && arr[index].t == value ? index : index - 1;
}

In conclusion, it's good to work with the simplest possible building blocks. binarySearchNearest has extra logic to make the result "nearest", which makes it a bit harder to understand, and it also increased the mental burden in its callers.

Generalize the sorting order

Currently there are multiple places in the code that refer to the .t property of the elements, used as the search key. This makes the otherwise generic binary search logic only applicable for the specific use case of items that have a numeric .t property. Also, if you ever need to change that property (for example to something more descriptive), then you'll have to change it on many lines.

You could generalize this using a key function that maps an item to the value to use to determine sorting order, and passing that function as a parameter to the search algorithm:

function binarySearch(arr, target, keyFunction) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    const value = keyFunction(arr[mid]);
    if (target < value) {
      hi = mid - 1;
    } else if (target > value) {
      lo = mid + 1;
    } else {
      return mid;
    }
  }

  return lo;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Ah, this makes complete sense! And it seems to work perfectly as well. Thanks a bunch! \$\endgroup\$ Oct 31 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.