数据二分查找

二分查找，或二分搜索，可以在排序数组中快速找到给定值。它通常用于查找将新值插入数组的位置，同时保持排序顺序。

bisector(accessor)

示例 · 源代码 · 使用指定的 accessor 函数返回一个新的二分查找器。

const bisector = d3.bisector((d) => d.Date);

如果给定的 accessor 接受两个参数，则它被解释为比较数据中的元素 d 与搜索值 x 的比较器函数。如果你想要按与自然顺序不同的顺序对值进行排序（例如，降序而不是升序），请使用比较器而不是访问器。上述代码等价于

const bisector = d3.bisector((d, x) => d.Date - x);

二分查找器可用于对对象排序数组进行二分查找（与 bisect 相反，它用于对基本数据类型进行二分查找）。

bisector.right(array, x, lo, hi)

d3.bisector((d) => d.Date).right(aapl, new Date("2014-01-02")) // 163

与 bisectRight 相似，但使用此二分查找器的访问器。上面的代码在 aapl 样本数据集 中找到了紧随 2014 年 1 月 2 日之后的那一行索引。

bisector.left(array, x, lo, hi)

d3.bisector((d) => d.Date).left(aapl, new Date("2014-01-02")) // 162

与 bisectLeft 相似，但使用此二分查找器的访问器。上面的代码在 aapl 样本数据集 中找到了 2014 年 1 月 2 日的那一行索引。

bisector.center(array, x, lo, hi)

d3.bisector((d) => d.Date).center(aapl, new Date("2013-12-31")) // 161

返回给定排序 array 中与 x 最接近的值的索引。这需要二分查找器的访问器返回一个量化值，或者二分查找器的比较器返回一个有符号距离；否则，此方法等效于 bisector.left。参数 lo（包含）和 hi（不包含）可用于指定要考虑的数组子集；默认情况下使用整个数组。

bisect(array, x, lo, hi)

d3.bisect(aapl.map((d) => d.Date), new Date("2014-01-02")) // 163

是 bisectRight 的别名。

bisectRight(array, x, lo, hi)

d3.bisectRight(aapl.map((d) => d.Date), new Date("2014-01-02")) // 163

与 bisectLeft 相似，但返回一个插入点，该插入点位于 array 中任何与 x 等效的现有条目之后（右侧）。返回的插入点 i 将 array 分成两半，使得 array.slice(lo, i) 中的所有 v <= x 位于左侧，而 array.slice(i, hi) 中的所有 v > x 位于右侧。另请参见 bisector.right.

bisectLeft(array, x, lo, hi)

d3.bisectLeft(aapl.map((d) => d.Date), new Date("2014-01-02")) // 162

返回 x 在 array 中的插入点以保持排序顺序。参数 lo 和 hi 可用于指定要考虑的数组子集；默认情况下使用整个数组。如果 x 已经存在于 array 中，则插入点将位于任何现有条目之前（左侧）。返回值适合用作 array.splice 的第一个参数，假设 array 已经排序。返回的插入点 i 将 array 分成两半，使得 array.slice(lo, i) 中的所有 v < x 位于左侧，而 array.slice(i, hi) 中的所有 v >= x 位于右侧。另请参见 bisector.left.

bisectCenter(array, x, lo, hi)

d3.bisectCenter(aapl.map((d) => d.Date), new Date("2013-12-31")) // 161

返回给定数字 array 中与 x 最接近的值的索引。参数 lo（包含）和 hi（不包含）可用于指定要考虑的数组子集；默认情况下使用整个数组。另请参见 bisector.center.