Javascript's equivalent of R's findInterval() or Python's bisect.bisect_left

Question

I can't find how to determine to which interval an element belongs based on an Array for JavaScript. I want the behavior of bisect.bisect_left from Python. Here is some sample code:

import bisect
a = [10,20,30,40]
print(bisect.bisect_left(a,0))  #0  because 0 <= 10
print(bisect.bisect_left(a,10)) #0  because 10 <= 10
print(bisect.bisect_left(a,15)) #1  because 10 < 15 < 20
print(bisect.bisect_left(a,25)) #2  ...
print(bisect.bisect_left(a,35)) #3  ...
print(bisect.bisect_left(a,45)) #4

I know this would be easy to implement, but why re-invent the wheel?

Answer 1

Speaking of re-inventing the wheel, I'd like to join the conversation:

function bisectLeft(arr, value, lo=0, hi=arr.length) {
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < value) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

I believe that is the schoolbook implementation of bisection. Actually, you'll find something pretty much the same inside the d3-array package mentioned before.