Incorrect results for binary search on large arrays due to miscomputation of midpoint
维护者通常 1 天内回复
评估
- 难度
- 2/5
- 预计耗时
- 1-3 小时
- 新手友好度
- 25/100
- Issue 类型
- 缺陷
- 描述清晰度
- 描述清楚
- 活跃度
- 停滞
- 技术栈
- javascript
- 领域
- search
调研方向
Start in src/bisector.js at bisector.left and bisector.right, where the issue identifies the midpoint calculation, and review the linked Observable example. Check the project’s relevant tests for large arrays and floating point bounds; done means both search methods return correct results for the reported case. A pull request is already open against this issue.
由索引模型根据 Issue 内容生成。
描述
I think I've spotted a bug in d3's binary search implementations that arises due to the use of unsigned bit shifts for the midpoint computation, which is a good approach when the numbers are actually unsigned integers, but not when they're floats:
https://observablehq.com/d/229d8bcf448308b9
If I've understood the problem correctly, the fix is simple, replacing
const mid = (lo + hi) >>> 1;
in bisector.left and bisector.right with
const mid = Math.floor(lo + (hi - lo) / 2)
- 主要语言
- JavaScript
- 星标
- 465
- 派生
- 193
- 平均合并
- 5 小时 46 分钟
- 30 天内合并 PR
- 1
环境准备
这个项目没有提供开发容器、Dockerfile 或贡献指南，环境需要你自己搭建：先看它的 README，通用步骤见我们的新手贡献指南。
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
d3/d3-array 的其他 Issue
-
d3.nice(start, stop, 1) returns [-1e308, 1e308] when the interval contains zero, so d3.bin gives NaN bin bounds可能已有人在做 @awais-ur-rehman 于 4 天前认领。 未关闭
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 1 天内回复
-
regression: in d3.bin, values next to a threshold go into the wrong bin可能已有人在做 @Fil 于 2 天前认领。 未关闭
d3/d3-array#295 · 1 个 reaction · 已指派 1 人 ·
维护者通常 1 天内回复
-
regression: d3.bin's last bin is twice as wide when the maximum is a threshold可能已有人在做 @Fil 于 2 天前认领。 未关闭
维护者通常 1 天内回复
-
难度 3/5 1-2 天 新手友好度 35/100
维护者通常 1 天内回复
-
groupSort should use ascendingDefined instead of ascending可能已有人在做 @cpruijsen 于 58 天前认领。 未关闭
难度 1/5 1 小时以内 新手友好度 10/100
维护者通常 1 天内回复
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 1 天内回复
-
0. Needs triage bug feature: api
难度 2/5 1-3 小时 新手友好度 78/100
维护者通常 1 天内回复
-
agent-os ai bug good first issue help wanted
难度 1/5 1-3 小时 新手友好度 68/100
维护者通常 1 天内回复
-
area: documentation good first issue package: rule-data status: accepting prs
难度 2/5 1-3 小时 新手友好度 72/100
维护者通常 1 天内回复
-
status: needs triage
难度 2/5 1-3 小时 新手友好度 85/100
mastra-ai/mastra#30109 · 2 条评论 ·
维护者通常 1 天内回复