2c:null 2d:["$","title",null,{"children":"d3.bisect | D3 | Observable"}] 32:T664,{ const height = 150; const x = d3 .scaleLinear() .domain(d3.extent(data, d => d.date)) .range([10, width - 10]); const y = d3 .scaleLog() .domain(d3.extent(data, d => d.close)) .rangeRound([height, 0]); const line = d3 .line() .x(d => x(d.date)) .y(d => y(d.close)); const chart = d3 .create("svg") .attr("width", width) .attr("height", height); chart .append("path") .attr("stroke", "black") .attr("fill", "none") .attr("d", line(data)); if (!mutable lookup) mutable lookup = new Date(data[400].date); const bar = chart .append("line") .attr("style", "stroke:#999; stroke-width:0.5; stroke-dasharray: 5 3;") .attr("y2", height) .attr("x1", x(mutable lookup)) .attr("x2", x(mutable lookup)); const legend = chart .append("text") .style("font", "12px sans-serif") .attr("x", 10) .attr("y", 140); const marker = chart .append("circle") .attr("r", 4) .attr("cx", -100) .attr("fill", "none") .attr("stroke", "red"); const formatTime = d3.timeFormat("%Y-%m-%d"); function update(date) { const i = bisect.right(data, date); if (i < data.length) { legend.text(`${formatTime(data[i].date)}: $${data[i].close}`); marker.attr("cx", x(data[i].date)).attr("cy", y(data[i].close)); } mutable lookup = new Date(date); bar.attr("x1", x(mutable lookup)).attr("x2", x(mutable lookup)); } chart.on("pointermove click", function(event) { const m = d3.pointer(event, this); update(x.invert(m[0])); }); update(mutable lookup); return chart.node(); }33:T5b0,{ const height = 250; const chart = d3 .create("svg") .attr("width", width) .attr("height", height); yield chart.node(); const y = d3 .scaleLinear() .domain([0, 12]) .range([10, height - 10]), extent = d3.extent(data, d => d.date), x = d3 .scaleLinear() .domain(extent) .range([10, width - 10]); function X(pos) { return x(pos < data.length ? data[pos].date : extent[1]); } const last = positions.length - 1, l = positions[last]; chart .append("line") .attr("y2", height) .attr("style", "stroke:#999; stroke-width:0.5; stroke-dasharray: 5 3;") .attr("x1", X(l)) .attr("x2", X(l)); chart .append("g") .selectAll("line") .data(d3.pairs(positions)) .join("line") .attr("x1", d => X(d[0])) .attr("x2", d => X(d[1])) .attr("y1", (_, i) => y(i)) .attr("y2", (_, i) => y(i + 1)) .style("stroke", "#ccc"); chart .append("g") .selectAll("circle") .data(positions.slice(0, -1)) .join("circle") .attr("r", 2) .attr("cx", d => X(d)) .attr("cy", (_, i) => y(i)); chart .append("circle") .attr("r", 3) .attr("cx", X(l)) .attr("cy", y(last)) .style("fill", "red"); chart.on("pointermove click", function(event) { const m = d3.pointer(event, this); const date = x.invert(m[0]); const i = bisect.right(data, date); mutable lookup = new Date(date); }); }34:[] 30:{"id":"8e91df5b8bf06458","slug":"d3-bisect","title":"d3.bisect","thumbnail":"6347862682df9d814f7b09bb25d0b547495d94f375ed3c948a2d193afbef3d9b","access_level":"public","create_time":"$D2019-03-22T07:05:08.416Z","update_time":"$D2024-07-01T15:46:28.997Z","view_time":null,"first_public_time":"$D2019-06-11T13:27:27.453Z","fork":{"id":"27fb05eac1212c56","slug":"d3-mean-d3-median-and-friends","title":"d3.mean, d3.median, and friends","owner":{"id":"863951e3ebe4c0ae","login":"d3","name":"D3"}},"stars":28,"starred":false,"owner":{"type":"team","id":"863951e3ebe4c0ae","login":"d3","name":"D3","avatar_url":"https://avatars-next.observableusercontent.com/5af16e327a90b2873351dda8a596c0d2d3bf954f64523deefe80177c9764d0f7","tier":"pro_2024"},"version":777,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"team","id":"863951e3ebe4c0ae","login":"d3","name":"D3","avatar_url":"https://avatars-next.observableusercontent.com/5af16e327a90b2873351dda8a596c0d2d3bf954f64523deefe80177c9764d0f7","tier":"pro_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":20,"collection":{"id":"1f9591a26e998ecc","slug":"d3-array","title":"d3-array","owner":{"id":"863951e3ebe4c0ae","login":"d3","name":"D3"}},"type":"notebook","body":{"title":"d3.bisect","cells":[{"id":0,"value":"# d3.bisect\n\n[d3.bisect](https://d3js.org/d3-array/bisect#bisect) finds the position into which a given value can be inserted into a sorted array while maintaining sorted order. If the value already exists in the array, d3.bisect will find its position efficiently.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":130,"value":"cents = d3.ticks(0, 10, 1000)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":132,"value":"index = d3.bisect(cents, Math.PI)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":204,"value":"[cents[index - 1], cents[index]]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":224,"value":"A typical use of d3.bisect is to build a sorted array of values progressively, using [*array*.splice](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice) to insert each new value at the correct position. Here, the values are represented by lines, with smaller values leaning left and larger values leaning right:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":310,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":226,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":247,"value":"sorted = {\n replay;\n const sorted = [];\n do {\n const x = Math.random();\n const i = d3.bisect(sorted, x);\n sorted.splice(i, 0, x); // insert \"x\" at rank i, deleting 0 element\n yield sorted;\n } while (sorted.length < 225);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":189,"value":"If more than one value in the array are equal to the search value, there are two strategies: d3.bisectLeft returns the lowest such position, while d3.bisectRight returns the highest position plus 1.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":155,"value":"d3.bisect([0, 1, 1, 2], 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":159,"value":"d3.bisectRight([0, 1, 1, 2], 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":157,"value":"d3.bisectLeft([0, 1, 1, 2], 1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":488,"value":"The default d3.bisect uses the d3.bisectRight strategy.\n\nWe can use these two methods to look for a range of repeated values in an array:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":454,"value":"numbers = Array.from({length: 1000}, (_, i) => Math.floor(Math.sqrt(i)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":469,"value":"n = 20","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":457,"value":"pos = [d3.bisectLeft(numbers, n), d3.bisectRight(numbers, n)]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":547,"value":"Result: _The number ${n} is repeated ${pos[1] -\n pos[0] -\n 1} times, for positions *i* where ${pos[0]} ≤ *i* < ${pos[1]}._\n\nIf the value is lower than array[0], d3.bisect returns 0; if it is higher than array[*length*-1], it returns *length*, a position that does not yet exist in the array.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":211,"value":"[d3.bisector](https://d3js.org/d3-array/bisect#bisector) creates a custom bisect function. In the following example, we're working from a list of (date, value) objects, sorted by ascending dates, and want to find the object under the mouse (for example to highlight it or show a pop-up window with details, as in this [line chart](https://observablehq.com/@d3/line-chart-with-tooltip)).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":323,"value":"// A synthetic dataset\n// to load your own, use data = d3.json(url)\n// or data = require(\"@observablehq/aapl\")\ndata = Array.from(\n (function*() {\n let date = new Date(\"2007-04-24\"),\n close = 98.84;\n for (let i = 0; i < 1280; i++) {\n if (i % 7 > 5) continue; // ignore 2 days per week\n date = new Date(date.setDate(date.getDate() + 1));\n close = +(close + Math.random() - 0.485).toFixed(2);\n yield { date, close };\n }\n })()\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":373,"value":"We can pass an accessor function to d3.bisector:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":327,"value":"bisect = d3.bisector(d => d.date)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":330,"value":"bisect.right(data, new Date(2010, 0, 9))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":345,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":280,"value":"### Algorithm\n\nd3.bisect uses the [bisection method](https://en.wikipedia.org/wiki/Bisection_method). This iterative algorithm begins with a target interval [lo, hi], and at each step compares the value with the array’s value at midpoint, where midpoint cuts [lo, hi] in half; the next interval is then [lo, midpoint] or [midpoint, hi], depending on the comparison’s result.\n\nThe following table shows the steps taken to locate the element that is under the mouse. First, when you move the mouse on the screen (or click), the mouse’s horizontal position (the red dot) is transformed to a date by the *x* scale’s invert, and reactively sent to the mutable cell *lookup*:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":618,"value":"mutable lookup = null","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":625,"value":"Next, this lookup value is compared to several elements of the array, in a sequence of binary choices ending with the insertion point:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":633,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":628,"value":"positions = [...bisectSteps(data, lookup, d => d.date)]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":632,"value":"At each step, the algorithm divides the search space in two; as such, it is guaranteed to reach the solution in about ${tex`\\lceil{\\log_2(n)}\\rceil`} steps, where *n* is the array’s length. That’s only 10 steps for 1024 values, and 20 steps for a million values!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":200,"value":"### Using a comparator\n\nd3.bisector can also create a bisector from a *comparator* function — the following example uses d3.descending to maintain values in an array sorted in descending order.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":382,"value":"{\n const sorted = [];\n const bisector = d3.bisector(d3.descending).right;\n do {\n const x = ((Math.random() * 1000) | 0) / 1000;\n const i = bisector(sorted, x);\n sorted.splice(i, 0, x); // inserts \"x\" at rank i, deleting 0 element\n yield sorted;\n } while (sorted.length < 255);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":587,"value":"The comparator function receives two values (*a*, *b*), where *a* is a test value taken from the existing array, and *b* is the new value that we want to insert.\n\nThe comparator should return:\n- –1 (or any non-positive number) if *b* must be inserted after *a*\n- 1 if *b* must be inserted before *a*\n- 0 if they are equivalent.\n\nIn the last case (0), the decision depends on whether you’re using the left- or right-handed version of the bisector.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":424,"value":"### [lo, hi] values\n\nd3.bisect can be called with explicit *lo*, *hi* values (defaults to: 0, *length*+1), thus restricting the search to a subset of *array*. These bounds are inclusive — the resulting insertion point is greater than or equal to *lo* and lower than or equal to *hi*:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":404,"value":"d3.bisect(cents, 4, 500, 700) // try different bounds!","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":684,"value":"d3.bisect(cents, 6, 500, 700)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":686,"value":"d3.bisect(cents, 8, 500, 700)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":571,"value":"### A note about iterables\n\nd3.bisect does not support iterables because it needs to have random access to the array to look up the elements in arbitrary positions. If your data is given by a finite iterable, use Array.from (or better, Float64Array.from) to transform it into an array. If the iterable is *not* finite, you’ll need a different insertion algorithm.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":4,"value":"---\n\n## Appendix\n\nThanks to [Maxene Graze](/@maxeneg) for suggestions.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":631,"value":"function* bisectSteps(a, x, accessor = d => d) {\n let lo = 0,\n hi = a.length;\n while (lo < hi) {\n var mid = (lo + hi) >>> 1;\n yield mid;\n if (d3.ascending(accessor(a[mid]), x) < 0) lo = mid + 1;\n else hi = mid;\n }\n yield lo;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 31:"$30:body"