Incorrect results for binary search on large arrays due to miscomputation of midpoint
Les mainteneurs répondent en général sous 1 jour
Évaluation
- Difficulté
- 2/5
- Temps estimé
- 1-3 heures
- Accessibilité débutants
- 25/100
- Type d'issue
- Bug
- Clarté
- Clairement spécifiée
- Activité
- À l'abandon
- Stack technique
- javascript
- Domaine
- search
Piste de recherche
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.
Rédigé par le modèle d'indexation à partir du texte de l'issue.
Description
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)
- Langage dominant
- JavaScript
- Étoiles
- 465
- Forks
- 193
- Merge moyen
- 5 h 46 min
- PR mergées (30 j)
- 1
Préparer son environnement
Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.
Par où commencer
- Lisez l'issue en entier, puis le guide de contribution du projet.
- Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
- Forkez le dépôt et travaillez sur une branche.
- Ouvrez une pull request qui référence le numéro de l'issue.
Autres issues de d3/d3-array
-
d3.nice(start, stop, 1) returns [-1e308, 1e308] when the interval contains zero, so d3.bin gives NaN bin boundsPeut-être pris @awais-ur-rehman l’a pris il y a 4 jours. Ouverte
Difficulté 2/5 1-3 heures Accessibilité débutants 78/100
Les mainteneurs répondent en général sous 1 jour
-
regression: in d3.bin, values next to a threshold go into the wrong binPeut-être pris @Fil l’a pris il y a 2 jours. Ouverte
d3/d3-array#295 · 1 réaction · 1 personne assignée ·
Les mainteneurs répondent en général sous 1 jour
-
regression: d3.bin's last bin is twice as wide when the maximum is a thresholdPeut-être pris @Fil l’a pris il y a 2 jours. Ouverte
d3/d3-array#294 · 1 personne assignée ·
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 3/5 1-2 jours Accessibilité débutants 35/100
d3/d3-array#280 · 2 commentaires ·
Les mainteneurs répondent en général sous 1 jour
-
groupSort should use ascendingDefined instead of ascendingPeut-être pris @cpruijsen l’a pris il y a 58 jours. Ouverte
Difficulté 1/5 Moins d'une heure Accessibilité débutants 10/100
Les mainteneurs répondent en général sous 1 jour
Toutes les issues de d3/d3-array
Issues similaires
-
Difficulté 2/5 1-3 heures Accessibilité débutants 78/100
Les mainteneurs répondent en général sous 1 jour
-
0. Needs triage bug feature: api
Difficulté 2/5 1-3 heures Accessibilité débutants 78/100
Les mainteneurs répondent en général sous 1 jour
-
agent-os ai bug good first issue help wanted
Difficulté 1/5 1-3 heures Accessibilité débutants 68/100
Les mainteneurs répondent en général sous 1 jour
-
area: documentation good first issue package: rule-data status: accepting prs
Difficulté 2/5 1-3 heures Accessibilité débutants 72/100
Les mainteneurs répondent en général sous 1 jour
-
status: needs triage
Difficulté 2/5 1-3 heures Accessibilité débutants 85/100
mastra-ai/mastra#30109 · 2 commentaires ·
Les mainteneurs répondent en général sous 1 jour