{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Algorithm{{ algorithmLabel }} Values{{ resultsReady ? canonicalSequence.length : '—' }} Target{{ resultsReady ? computation.normalizedInputs.target : '—' }}
{{ stageStateLabel }}{{ stageMarker }}
  1. {{ cell.index }}{{ cell.value }}{{ cell.state }}
Every method reports the lowest matching index when duplicates exist.
Manual order is preserved; generated values are always ascending.
Example: 1, 4, 4, 4, 8, 13, 21
Whole number from -9999 to 9999.
{{ playbackLabel }}{{ playback_delay }} ms
The neutral default is 700 ms between steps.
StepProbeDecisionCandidate rangeExplanationCopy
{{ row.step }}{{ row.probe }}{{ row.decision }}{{ row.range }}{{ row.explanation }}

The chart renderer is unavailable. The same probe counts remain in the trace ledger.

AlgorithmCompatibleProbesOutcomeCopy
{{ row.label }}{{ row.compatible ? 'Yes' : 'No' }}{{ row.compatible ? row.probes : '—' }}{{ row.outcome }}
Sorting Algorithm Simulator Step through eight sorting algorithms on entered or seeded arrays with verified order, stability and operation counts for each deterministic run.
BST Operations Simulator Trace BST operations from insertion and search through deletion and traversal across ordinary, AVL or red-black trees with invariant checks and replay.
Pathfinding Algorithm Simulator Compare four pathfinding algorithms on an editable weighted grid and inspect route cost, exploration order, diagonal rules and no-path outcomes.
String Matching Algorithm Simulator Compare four exact string-matching methods with Unicode traces showing preprocessing and shifts plus overlap and hash-collision handling.

Searching an indexed sequence means locating a target value or proving that it is absent. The same result can require very different work depending on the order of the data and the next index chosen for inspection. A method that skips large parts of an ascending array can save probes, but that shortcut becomes invalid when the values are out of order.

Linear search makes no ordering assumption and checks values from left to right. Binary search repeatedly halves an ascending candidate range. Jump search checks block ends and then scans the first block that could contain the target. Interpolation search uses the values at the range endpoints to estimate where the target may lie.

Method Required order How it chooses the next probe Useful teaching contrast
LinearAny orderNext index from the leftReliable baseline with no skipped candidates
BinaryAscendingMiddle of the active rangeValue order eliminates about half the range per comparison
JumpAscendingEnd of a square-root-sized block, then a short linear scanBlock skipping followed by local inspection
InterpolationAscendingPosition estimated from the target and endpoint valuesDistribution affects how useful the estimate is

Duplicates introduce a second question after a match appears: is it the first matching index? A midpoint or estimate may land on a later duplicate. A lowest-index search remembers that candidate and continues left until no smaller matching index remains.

Probe counts compare work within this particular model and input. They are not elapsed time and do not include memory layout, branch prediction, cache behavior, vectorization, or the cost of preparing sorted data. A method with fewer probes in a short simulation is not automatically faster in every program.

Generated sequences are useful for repeatable experiments because a fixed size, distribution, and seed produce the same ascending values. Manual sequences are better when the exact duplicates, gaps, or disorder are the subject of the lesson.

How to Use This Tool:

Choose the data source before comparing methods so every probe trace answers the same search question.

  1. Select Linear, Binary, Jump, or Interpolation under Algorithm.
  2. Choose Manual under Sequence source to enter 1 to 48 integers from -9,999 to 9,999. Binary, jump, and interpolation search require ascending values; reorder the sequence or choose linear search when validation reports otherwise.
  3. Choose Generated to create 4 to 32 ascending values. Set Distribution and Generation seed; the same settings reproduce the same sequence.
  4. Enter the Target integer, then start or step through the trace. The active range, probe, eliminated indices, remembered candidate, and comparison decision show how the result develops.
  5. Use Algorithm comparison only after confirming every compared method is compatible with the sequence order. Keep the sequence and target fixed when probe counts are the comparison.

Interpreting Results:

First match is a zero-based index, so index 0 means the first value in the sequence. A result of -1 means the active candidate range became empty without a match. The probe count includes inspected sequence values, not the initial setup frame.

For duplicate values, all four methods are adjusted to report the lowest matching index. Binary and interpolation search may first encounter a later duplicate, remember it, and continue in the remaining left range. A visible candidate is therefore provisional until the trace confirms that no lower match remains.

Distribution changes interpolation behavior most directly because its estimate depends on endpoint values. Compare methods on several repeatable sequences before drawing a broad efficiency conclusion.

Technical Details:

Every trace maintains an inclusive active range from low to high. A comparison either records a match candidate, removes indices that cannot contain the target, or ends with an empty range. Eliminated indices never re-enter the search.

Rule Core:

Method Comparison rule First-match handling Miss condition
LinearInspect each index from 0 upward.Stop at the first equality.Every index has been inspected.
BinaryIf the midpoint is below the target, remove the midpoint and everything left of it; otherwise continue left.Remember an equal midpoint and search the lower indices.low becomes greater than high without a candidate.
JumpProbe block ends until one is at least the target, then scan that block from left to right.The block scan stops at its first equality.All blocks are skipped, or the scan passes the only possible position.
InterpolationEstimate a probe from endpoint values, remove the impossible side, and repeat while the target remains within the endpoint values.Remember equality and interpolate the remaining left range.The index range empties or the target falls outside its endpoint values.

Formula Core:

Binary search chooses its midpoint without adding the endpoints first, avoiding integer overflow in fixed-width implementations.

mid=low+ ⌊high−low2⌋

Jump search uses the integer square root of the sequence length, with a minimum block width of 1.

j=max(1,⌊n⌋)

Interpolation search estimates a position from the target's relative distance between the values at the active endpoints.

probe=low+⌊ (target−Alow)(high−low) Ahigh−Alow ⌋

If both endpoint values are equal, interpolation probes low instead of dividing by zero. The estimate is clamped to the inclusive active range. Generated values use deterministic whole-number gaps; manual values retain their entered order.

Duplicate Example:

In 1, 4, 4, 4, 8, 13, 21, searching for 4 must return index 1 even if a midpoint or estimate first lands on index 2 or 3. Continuing left after equality distinguishes a first-match trace from a search that accepts any matching index.

Playback delay changes only animation timing. It does not change the sequence, probe order, match index, or operation counts.

References:

  • Linear search, NIST Dictionary of Algorithms and Data Structures, entry modified April 21, 2022.
  • Binary search, NIST Dictionary of Algorithms and Data Structures, entry modified April 21, 2022.
  • Jump search, NIST Dictionary of Algorithms and Data Structures, entry modified September 3, 2019.
  • Interpolation search, NIST Dictionary of Algorithms and Data Structures, entry modified March 4, 2019.