Bisection Method

Finds a root by repeatedly halving a bracketing interval where the function changes sign.

Author

Dhruv Azad

Published

June 25, 2026

// VM is the shared utility library, loaded globally via _includes/head-scripts.html (js/**). This page uses VM.numerical.linearRegression, VM.expressions.makeFunction, VM.expressions.makeNumber, VM.plotting.paddedRange, VM.ui.renderTable, VM.ui.applyExampleParams.
VM = window.VM

traceOptions = ["f(x)", "Previous midpoints", "Endpoints", "Midpoint", "Exact root found"]

// Matches the line/marker colors mainPlot uses for each trace, so the
// overlay legend's swatches double as a color key. #f97316 (orange) has no
// VM.plotting.colors() token -- left as a literal, same as other
// beyond-the-core-palette accents elsewhere on the site (e.g. k-means'
// extra cluster hues).
// vmTheme is what makes the colors below reactive. The chart's own chrome
// (background, axes, gridlines) repaints on a dark-mode toggle by itself,
// via the relayout patch in plotly-fullscreen-button.js -- but the *trace*
// colors are values this page bakes into the traces it builds, so nothing
// repaints them unless mainPlot re-runs. Depending on vmTheme is what
// re-runs it. See VM.plotting.onThemeChange for why it fires a couple of
// frames after the toggle rather than inline.
vmTheme = Generators.observe(notify => VM.plotting.onThemeChange(notify))

chartColors = VM.plotting.colors(vmTheme)

traceColors = new Map([
  ["f(x)", chartColors.fn],
  ["Previous midpoints", "#f97316"],
  ["Endpoints", chartColors.fn],
  ["Midpoint", chartColors.alt],
  ["Exact root found", chartColors.ok]
])

// examples backs the "Try an example" dropdown near the top controls.
examples = [
  {
    title: "Choosing one root among many",
    params: {max: "20", f: "(x - 1)*(x - 2)*(x - 3)", a: "0.3", b: "3.4"}
  },
  {
    title: "Same function, different bracket",
    params: {max: "20", f: "(x - 1)*(x - 2)*(x - 3)", a: "2.4", b: "3.5"}
  },
  {
    title: "Standard guaranteed convergence",
    params: {max: "20", f: "x^3 - x - 2", a: "1", b: "2"}
  },
  {
    title: "Sign change without a valid root",
    params: {max: "20", f: "1/x", a: "-1", b: "1"}
  }
]

viewof fText = {
  const params = new URLSearchParams(window.location.search)
  const fTextInput = Inputs.text({label: "Function f(x)", value: params.get("f") ?? "(x - 1)*(x - 2)*(x - 3)", placeholder: "Example: x^3 - x - 2, cos(x) - x"})
  fTextInput.classList.add("ojs-fill")
  fTextInput.dataset.exampleField = "f"
  return fTextInput
}

// Plot commits the current function/endpoint fields — edits above don't
// take effect until this is clicked, so result/mainPlot don't recompute on
// every keystroke. The step slider overlaid on the plot is unaffected and stays reactive.
viewof plotTrigger = {
  const plotButton = Inputs.button("Plot", {value: 0, reduce: v => v + 1})
  plotButton.classList.add("ojs-auto")
  return plotButton
}

viewof a0 = {
  const params = new URLSearchParams(window.location.search)
  const a0Input = Inputs.text({label: "Left endpoint a", value: params.get("a") ?? "0.3", placeholder: "Example: 1, -pi/2"})
  a0Input.dataset.exampleField = "a"
  return a0Input
}

viewof b0 = {
  const params = new URLSearchParams(window.location.search)
  const b0Input = Inputs.text({label: "Right endpoint b", value: params.get("b") ?? "3.4", placeholder: "Example: 2, pi"})
  b0Input.dataset.exampleField = "b"
  return b0Input
}

// Always-live (not gated behind Plot) — it bounds the step slider rather
// than feeding result, so there's no reason to wait for a commit. Shares
// this row with the commit-gated fields now that a shorter label leaves
// room; see urlSyncControls below for how it stays in the URL.
viewof maxIterationsInput = {
  const input = Inputs.text({value: initialMax, label: "Max n", placeholder: "Example: 20, 5*4"})
  input.dataset.exampleField = "max"
  return input
}

viewof exampleSelect = {
  const options = [null, ...examples]
  const select = Inputs.select(options, {label: "Try an example", format: e => e ? e.title : "Pick an example…", value: null})
  select.classList.add("ojs-fill")
  return select
}

// Plain CSS selectors, not direct viewof references -- see
// js/ui/apply-example.js's comment for why.
exampleFieldSelectors = ({f: '[data-example-field="f"]', a: '[data-example-field="a"]', b: '[data-example-field="b"]', max: '[data-example-field="max"]'})

// Applies the selected example's params to the fields above and clicks
// Plot, in place — no page reload, so no scroll jump either. A plain
// "change" listener attached once to the stable native <select> (rather
// than an OJS cell reactive on exampleSelect's value) — a <select> fires
// both "input" and "change" per selection, and a reactive cell would run
// once per event, with two overlapping calls racing each other.
applyExampleFromSelect = {
  const nativeSelect = (viewof exampleSelect).querySelector("select")
  if (!nativeSelect) return
  nativeSelect.addEventListener("change", () => {
    const example = (viewof exampleSelect).value
    if (!example) return
    VM.ui.applyExampleParams(exampleFieldSelectors, example.params, viewof plotTrigger)
  })
}

// Pressing Enter in the function/endpoint fields clicks Plot instead of
// submitting the field's own (invisible) form. Depends only on the stable
// views, so this wiring runs once and is never re-attached.
enterToPlot = {
  for (const view of [viewof fText, viewof a0, viewof b0]) {
    const input = view.querySelector("input")
    if (!input) continue
    input.addEventListener("keydown", (e) => {
      if (e.key !== "Enter") return
      e.preventDefault()
      viewof plotTrigger.querySelector("button").click()
    })
  }
}

// committed snapshots fText/a0/b0 only when Plot is clicked, and writes them
// back into the URL so the address bar stays a shareable link. It reads
// `viewof fText`/`viewof a0`/`viewof b0` (the stable DOM views) rather than
// `fText`/`a0`/`b0` (the reactive values), so it does NOT rerun on every
// keystroke — only when `plotTrigger` changes. It still runs once on
// initial page load, so the first render uses the URL-provided (or
// default) values with no click.
committed = {
  plotTrigger
  const math = window.math
  const fVal = (viewof fText).value
  const aText = (viewof a0).value
  const bText = (viewof b0).value
  const aVal = VM.expressions.makeNumber(math, aText)
  const bVal = VM.expressions.makeNumber(math, bText)

  const params = new URLSearchParams(window.location.search)
  params.set("f", fVal)
  params.set("a", aText)
  params.set("b", bText)
  history.replaceState(null, "", `${window.location.pathname}?${params}`)

  return {fText: fVal, a0: aVal, b0: bVal}
}

// max is always-live rather than commit-gated, so it gets its own sync cell
// instead of piggybacking on committed above (which only runs when Plot is
// clicked).
urlSyncControls = {
  const params = new URLSearchParams(window.location.search)
  params.set("max", maxIterationsInput)
  history.replaceState(null, "", `${window.location.pathname}?${params}`)
  return true
}

// result: runs bisection with the current committed inputs.
//   rows — array of { n, a, b, m, fa, fb, fm, width }, one entry per iteration
//   f    — parsed function, reused for curve sampling in setup
result = {
  const math = window.math

  const f        = VM.expressions.makeFunction(math, committed.fText)
  const fallback = x => NaN

  if (!f) return {rows: [], f: fallback}

  let a = committed.a0
  let b = committed.b0

  if (!Number.isFinite(a) || !Number.isFinite(b) || a === b) return {rows: [], f}
  if (a > b) { const temp = a; a = b; b = temp }   // ensure a < b

  const fa = f(a)
  const fb = f(b)

  if (!Number.isFinite(fa) || !Number.isFinite(fb)) return {rows: [], f}

  // Bisection requires a sign change across [a, b].
  // If an endpoint is already a root, return it immediately.
  if (fa === 0) return {rows: [{n: 0, a, b, m: a, fa, fb, fm: fa, width: b - a}], f}
  if (fb === 0) return {rows: [{n: 0, a, b, m: b, fa, fb, fm: fb, width: b - a}], f}
  if (fa * fb > 0) return {rows: [], f}   // no sign change — can't bracket a root

  const rows = []
  let curA = a, curB = b, curFa = fa, curFb = fb
  let n = 0
  while (n < maxIterations) {
    const m  = 0.5 * (curA + curB)   // midpoint of the current bracket
    const fm = f(m)
  rows.push({n, a: curA, b: curB, m, fa: curFa, fb: curFb, fm, width: curB - curA})
  
  if (!Number.isFinite(fm)) return {rows, f}
  
  // If the midpoint is exactly a root, stop.
  // Otherwise the code would keep iterating even though the root was found.
  if (fm === 0) return {rows, f}
  
  // Keep the half that still contains a sign change.
  if (curFa * fm < 0) {
    curB = m
    curFb = fm
  } else {
    curA = m
    curFa = fm
  }
  n++
  }
  return {rows, f}
}

// setup computes the data shared by all three plots below: which rows are
// visible at the current step, and the axis ranges / curve samples for the
// main chart.
setup = {
  const visibleRows = result.rows.slice(0, Math.min(Number(stepControl), result.rows.length) + 1)
  const currentRow  = visibleRows.length === 0 ? null : visibleRows[visibleRows.length - 1]

  // Axis ranges from ALL rows so the axes stay fixed while stepping.
  const xValues = [committed.a0, committed.b0]
  for (const row of result.rows) xValues.push(row.a, row.b, row.m)
  const xRange = VM.plotting.paddedRange(xValues, {emptyRange: [-5, 5], relativePadding: 0.25, minPadding: 0.5})

  // A wider domain (double the padding of xRange) so the curve is already
  // sampled beyond the initial view — panning/zooming out reveals more of
  // the curve instead of blank canvas. The initial view stays xRange.
  const xBuffer = VM.plotting.paddedRange(xValues, {emptyRange: [-10, 10], relativePadding: 0.5, minPadding: 1.0})

  // Sample f across the buffer range for the smooth curve trace.
  const sampleCount = 700
  const sampleXs = Array.from({length: sampleCount}, (_, i) => xBuffer.lo + (xBuffer.hi - xBuffer.lo) * i / (sampleCount - 1))
  const sampleYs = []
  for (const x of sampleXs) {
    const y = result.f(x)
    if (Number.isFinite(y) && Math.abs(y) < 1e8) {
      sampleYs.push(y)
    } else {
      sampleYs.push(null)
    }
  }

  // Cap row values at 1e8 so a near-singularity doesn't blow up the axis range.
  // Only samples within the initial view (xRange) count, so yRange — and
  // the initial view — stay unaffected by the wider sampling.
  const yValues = [0]
  for (let i = 0; i < sampleXs.length; i++) {
    const x = sampleXs[i]
    if (x >= xRange.lo && x <= xRange.hi && sampleYs[i] !== null) yValues.push(sampleYs[i])
  }
  for (const row of result.rows) {
    for (const v of [row.fa, row.fb, row.fm]) {
      if (Number.isFinite(v) && Math.abs(v) <= 1e8) yValues.push(v)
    }
  }
  const yRange = VM.plotting.paddedRange(yValues, {emptyRange: [-1, 1], relativePadding: 0.25, minPadding: 0.5})

  return {visibleRows, currentRow, xRange, xBuffer, yRange, sampleXs, sampleYs}
}

// mainPlot draws f(x), the current bracket [a, b], and the midpoint.
//
// _plotDiv is kept in a closure so Plotly reuses the same DOM node across
// reactive updates — this preserves zoom and pan when the step changes.
mainPlot = {
  const Plotly = window.Plotly
  let _plotDiv = null

  return ({visibleRows, currentRow, xRange, xBuffer, yRange, sampleXs, sampleYs}, showFCurve, showPrevMidpoints, showEndpoints, showMidpoint, showExactRoot) => {
    const data = []

    if (showFCurve) {
      // The function curve
      data.push({x: sampleXs, y: sampleYs, type: "scatter", mode: "lines", name: "f(x)", showlegend: false, line: {color: chartColors.fn, width: 3}})
    }

    // Previous midpoints — all steps before the current one
    const prevRows = []
    for (const r of visibleRows.slice(0, -1)) {
      if (Number.isFinite(r.m) && Number.isFinite(r.fm)) prevRows.push(r)
    }
    if (showPrevMidpoints && prevRows.length > 0) {
      const xs = [], ys = [], labels = []
      for (const r of prevRows) {
        xs.push(r.m)
        ys.push(r.fm)
        labels.push(`m${r.n}`)
      }
      data.push({
        x: xs, y: ys,
        type: "scatter", mode: "markers+text", name: "Previous midpoints", showlegend: false,
        text: labels, textposition: "top center",
        marker: {color: "#f97316", size: 8, symbol: "circle", line: {color: chartColors.halo, width: 1}}
      })
    }

    if (currentRow) {
      const row = currentRow
      if (showEndpoints) {
        data.push(
          // Endpoints a and b
          {x: [row.a, row.b], y: [row.fa, row.fb], type: "scatter", mode: "markers+text", name: "Endpoints",
            text: ["a", "b"], textposition: "top center", showlegend: false,
            marker: {color: chartColors.fn, size: 11, symbol: "circle", line: {color: chartColors.halo, width: 1}}},
          // Dotted verticals from x-axis to the endpoint markers
          {x: [row.a, row.a], y: [0, row.fa], type: "scatter", mode: "lines", showlegend: false, hoverinfo: "skip", line: {color: chartColors.muted, width: 1.5, dash: "dot"}},
          {x: [row.b, row.b], y: [0, row.fb], type: "scatter", mode: "lines", showlegend: false, hoverinfo: "skip", line: {color: chartColors.muted, width: 1.5, dash: "dot"}}
        )
      }
      if (showMidpoint) {
        data.push(
          // Current midpoint m
          {x: [row.m], y: [row.fm], type: "scatter", mode: "markers+text", name: "Midpoint",
            text: [`m${row.n}`], textposition: "top center", showlegend: false,
            marker: {color: chartColors.alt, size: 13, symbol: "circle", line: {color: chartColors.halo, width: 1}}},
          // Dotted vertical from x-axis to the midpoint marker
          {x: [row.m, row.m], y: [0, row.fm], type: "scatter", mode: "lines", showlegend: false, hoverinfo: "skip", line: {color: chartColors.alt, width: 1.5, dash: "dot"}}
        )
      }
      // If the current midpoint is exactly a root, add a prominent success marker.
      if (showExactRoot && row.fm === 0) {
        data.push({
          x: [row.m],
          y: [0],
          type: "scatter",
          mode: "markers+text",
          name: "Exact root found",
          text: ["root"],
          textposition: "bottom center",
          showlegend: false,
          marker: {
            color: chartColors.ok,
            size: 16,
            symbol: "star",
            line: {color: chartColors.halo, width: 1.5}
          }
        })
      }
    }

    // Shaded rectangle showing the current bracket [a, b]
    let shapes = []
    if (currentRow) {
      shapes = [{
        type: "rect", xref: "x", yref: "paper",
        x0: currentRow.a, x1: currentRow.b, y0: 0, y1: 1,
        fillcolor: "rgba(37, 99, 235, 0.14)", line: {width: 0}
      }]
    }

    const layout = {
      xaxis: {title: "x", range: [xRange.lo, xRange.hi], zeroline: true},
      yaxis: {title: "f(x)", range: [yRange.lo, yRange.hi], zeroline: true},
      shapes,
      hovermode: "closest",
      uirevision: "static",  // keeps zoom/pan state across reactive updates
      autosize: true
    }
    const config = VM.plotting.config()

    // First render: create the div. Later renders: update in place (preserves zoom).
    if (!_plotDiv) {
      _plotDiv = document.createElement("div")
      _plotDiv.className = "plotly-box-large"
      Plotly.newPlot(_plotDiv, data, layout, config)
      VM.plotting.autoResize(_plotDiv)
    } else {
      Plotly.react(_plotDiv, data, layout, config)
    }
    return _plotDiv
  }
}

// maxIterations parses the Max field's expression, falling back to 20 for
// invalid input so the step slider and result loop always get a usable bound.
maxIterations = {
  const math = window.math
  const parsed = VM.expressions.makeNumber(math, maxIterationsInput)
  if (parsed === null || !Number.isFinite(parsed)) return 20
  return Math.max(1, Math.round(parsed))
}

mainPlot(setup, showFCurve, showPrevMidpoints, showEndpoints, showMidpoint, showExactRoot)

viewof traces = {
  const items = []
  for (const label of traceOptions) items.push({label, color: traceColors.get(label)})
  return VM.ui.legendOverlay(items, {value: traceOptions})
}

viewof stepControl = {
  const stepSlider = Inputs.range([0, maxIterations - 1], {step: 1, value: 0, label: "n"})
  stepSlider.classList.add("ojs-fill")
  return stepSlider
}

Convergence plots

// iteratesPlot draws the midpoint mₙ vs n for the entire run — it doesn't
// depend on the current step, so it's just plotted once per run.
iteratesPlot = {
  const midpointAccessor = row => {
    if (Number.isFinite(row.m)) return row.m
    return null
  }
  return Plot.plot({
    width: 340, height: 300, marginLeft: 46,
    x: {label: "n"},
    y: {label: "mₙ"},
    marks: [
      Plot.lineY(result.rows, {x: "n", y: midpointAccessor, stroke: chartColors.fn}),
      Plot.dot(result.rows, {x: "n", y: midpointAccessor, fill: chartColors.fn, r: 4})
    ]
  })
}
// convergencePlot draws log₁₀|f(mₙ)| vs n (semi-log) with a linear
// regression line, for the entire run — it doesn't depend on the current
// step, so it's just plotted once per run.
convergencePlot = {
  const finiteLogRows = []
  const exactZeroRows = []

  for (const r of result.rows) {
    if (!Number.isFinite(r.fm)) continue

    if (r.fm === 0) {
      exactZeroRows.push(r)
    } else {
      finiteLogRows.push({n: r.n, y: Math.log10(Math.abs(r.fm))})
    }
  }

  // log10(0) is -Infinity, so exact roots cannot be plotted literally.
  // Instead, place exact-zero residuals one decade below the smallest
  // nonzero residual, or at -16 if there are no nonzero residuals.
  let zeroPlotY = -16
  if (finiteLogRows.length > 0) {
    zeroPlotY = Math.min(...finiteLogRows.map(d => d.y)) - 1
  }

  const zeroRows = exactZeroRows.map(r => ({
    n: r.n,
    y: zeroPlotY,
    label: "exact root"
  }))

  const pointsName = "log₁₀|f(mₙ)|"
  const exactName = "f(mₙ) = 0"

  const marks = [
    Plot.dot(finiteLogRows, {x: "n", y: "y", fill: () => pointsName, r: 4})
  ]

  const colorDomain = [pointsName], colorRange = [chartColors.alt]

  if (zeroRows.length > 0) {
    marks.push(
      Plot.dot(zeroRows, {x: "n", y: "y", fill: () => exactName, r: 6, symbol: "star"}),
      Plot.text(zeroRows, {x: "n", y: "y", text: "label", dy: -10, fill: chartColors.ok})
    )
    colorDomain.push(exactName)
    colorRange.push(chartColors.ok)
  }

  // legendDomain/legendRange hold only the regression line(s) — the legend
  // shown below the chart displays just the fitted slope, not the raw
  // point series, to keep it uncluttered.
  const legendDomain = [], legendRange = []

  const regressionPoints = []
  for (const row of finiteLogRows) regressionPoints.push({x: row.n, y: row.y})

  const fit = VM.numerical.linearRegression(regressionPoints)
  if (fit) {
    const lineName = `slope ≈ ${fit.slope.toFixed(2)}`
    marks.push(Plot.line(
      [{n: fit.xlo, y: fit.slope * fit.xlo + fit.intercept}, {n: fit.xhi, y: fit.slope * fit.xhi + fit.intercept}],
      {x: "n", y: "y", stroke: () => lineName, strokeDasharray: "6,4"}
    ))
    colorDomain.push(lineName)
    colorRange.push(chartColors.accent2)
    legendDomain.push(lineName)
    legendRange.push(chartColors.accent2)
  }

  const chart = Plot.plot({
    width: 340, height: 300, marginLeft: 46,
    x: {label: "n"},
    y: {label: "log₁₀|f(mₙ)|"},
    color: {domain: colorDomain, range: colorRange},
    marks
  })

  const container = document.createElement("div")
  container.append(chart)
  // Plot.legend throws on an empty domain/range — there's no legend to
  // show when the run didn't produce a regression line (e.g. a
  // non-converging example).
  if (legendDomain.length > 0) {
    const legend = Plot.legend({color: {domain: legendDomain, range: legendRange}})
    container.append(legend)
  }
  return container
}

Iteration table

// Iteration table — shows the entire run, not just the current step.
iterationTable = {
  if (result.rows.length === 0) {
    // Always return a Node so Quarto's OJS runtime never latches this
    // declaration cell as hidden.
    return document.createElement("div")
  }

  const formattedRows = []
  for (const row of result.rows) {
    let aCell = "NaN"
    if (Number.isFinite(row.a)) aCell = row.a.toPrecision(10)

    let bCell = "NaN"
    if (Number.isFinite(row.b)) bCell = row.b.toPrecision(10)

    let mCell = "NaN"
    if (Number.isFinite(row.m)) mCell = row.m.toPrecision(10)

    let faCell = "NaN"
    if (Number.isFinite(row.fa)) faCell = row.fa.toExponential(5)

    let fbCell = "NaN"
    if (Number.isFinite(row.fb)) fbCell = row.fb.toExponential(5)

    let fmCell = "NaN"
    if (Number.isFinite(row.fm)) fmCell = row.fm.toExponential(5)

    let widthCell = "NaN"
    if (Number.isFinite(row.width)) widthCell = row.width.toExponential(4)

    formattedRows.push([row.n, aCell, bCell, mCell, faCell, fbCell, fmCell, widthCell])
  }

  return VM.ui.renderTable({
    html,
    headers: ["n", tex`a_n`, tex`b_n`, tex`m_n`, tex`f(a_n)`, tex`f(b_n)`, tex`f(m_n)`, "width"],
    csvHeaders: ["n", "a_n", "b_n", "m_n", "f(a_n)", "f(b_n)", "f(m_n)", "width"],
    filename: "bisection-method-iterations.csv",
    rows: formattedRows
  })
}

The bisection method finds a root of \(f(x)=0\) by repeatedly halving an interval \([a_n,b_n]\) that brackets a sign change of \(f\), keeping whichever half still brackets it:

\[ m_n=\frac{a_n+b_n}{2},\qquad (a_{n+1},b_{n+1})= \begin{cases} (a_n,m_n) & f(a_n)f(m_n)<0,\\[2pt] (m_n,b_n) & \text{otherwise.} \end{cases} \]