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 天內回覆