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

Question

我找不到如何根据 JavaScript 的数组确定元素属于哪个区间。我想要 Python 中 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

比以前接受的适用于相同大小间隔的答案更快的方法是：

var array = [5, 20, 35, 50]

//Intervals:
//      <5: 0 
//  [5-20): 1
// [20-35): 2
// [35-50): 3
//    >=50: 4

var getPosition = function(array, x) {
  if (array.length == 0) return;
  if (array.length == 1) return (x < array[0]) ? 0 : 1;
  return Math.floor((x - array[0]) / (array[1] - array[0])) + 1
}

console.log(getPosition(array, 2)); //0
console.log(getPosition(array, 5)); //1
console.log(getPosition(array, 15));//1
console.log(getPosition(array, 20));//2
console.log(getPosition(array, 48));//3
console.log(getPosition(array, 50));//4
console.log(getPosition(array, 53));//4

console.log("WHEN SIZE: 1")
array = [5];
//Intervals:
//  <5: 0
// >=5: 1
console.log(getPosition(array, 3));
console.log(getPosition(array, 5));
console.log(getPosition(array, 6));

Answer 3

万一其他人在这里着陆，这里是 bisect_left 的一个实现，它实际上在 O(log N) 中运行，并且无论列表元素之间的间隔如何都应该工作。注意，not 对输入列表进行排序，并且，如果您将未排序的列表传递给它，可能会按原样破坏堆栈。它也只设置为使用数字，但应该很容易使其适应接受比较功能。以此为起点，不一定是您的目的地。欢迎改进！

Run it in a REPL

function bisect(sortedList, el){
  if(!sortedList.length) return 0;

  if(sortedList.length == 1) {
    return el > sortedList[0] ? 1 : 0;
  }

  let lbound = 0;
  let rbound = sortedList.length - 1;
  return bisect(lbound, rbound);

// note that this function depends on closure over lbound and rbound
// to work correctly
  function bisect(lb, rb){
    if(rb - lb == 1){
      if(sortedList[lb] < el && sortedList[rb] >= el){
        return lb + 1;
      }

      if(sortedList[lb] == el){
        return lb;
      }
    }

    if(sortedList[lb] > el){
      return 0;
    }

    if(sortedList[rb] < el){
      return sortedList.length
    }

    let midPoint = lb + (Math.floor((rb - lb) / 2));
    let midValue = sortedList[midPoint];

    if(el <= midValue){
      rbound = midPoint
    }

    else if(el > midValue){
      lbound = midPoint
    }

    return bisect(lbound, rbound);
  }
}

console.log(bisect([1,2,4,5,6], 3)) // => 2
console.log(bisect([1,2,4,5,6], 7)) // => 5
console.log(bisect([0,1,1,1,1,2], 1)) // => 1
console.log(bisect([0,1], 0)) // => 0
console.log(bisect([1,1,1,1,1], 1)) // => 0
console.log(bisect([1], 2)); // => 1
console.log(bisect([1], 1)); // => 0

Answer 4

使用 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));

输出：

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

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

javascript

python

bisection