Javascript相当于R的findInterval()或Python的bisect.bisect_left

Question

我找不到如何根据JavaScript的数组来确定元素属于哪个区间。我想要bisect.bisect_left的行为。下面是一些示例代码：

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

我知道这很容易实现，但为什么要重新发明轮子呢？

Answer 1

在JavaScript中没有内置的二分函数，所以您必须自己滚动。这是我个人对车轮的改造：

​

var array = [10, 20, 30, 40]

function bisectLeft (array, x) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] >= x) return i
  }
  return array.length
}

console.log(bisectLeft(array, 5))
console.log(bisectLeft(array, 15))
console.log(bisectLeft(array, 25))
console.log(bisectLeft(array, 35))
console.log(bisectLeft(array, 45))

function bisectRight (array, x) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] > x) return i
  }
  return array.length
}

​

Answer 2

使用D3数组npm。

const d3 = require('d3-array'); 

var a = [10,20,30,40];
console.log(d3.bisectLeft(a,0));  
console.log(d3.bisectLeft(a,10)); 
console.log(d3.bisectLeft(a,15));
console.log(d3.bisectLeft(a,25));
console.log(d3.bisectLeft(a,35));
console.log(d3.bisectLeft(a,45));

产出：

0
0
1
2
3
4

Answer 3

说到重新发明方向盘，我想加入到谈话中来：

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;
}

我相信这是教科书实施的二分法。实际上，您会在前面提到的d3数组包中找到一些差不多一样。