Jump Search

Jump search is the compromise between linear and binary. Instead of checking every element, or halving the whole array each time, it strides forward in fixed jumps of about the square root of the length and only looks at the last value in each block. As long as that value is still below the target, it skips the entire block and jumps again. The moment a block ends at or past the target, it stops jumping: the target, if it exists, has to be inside that one block.

Then it does the humble thing and walks that block from the left, one comparison at a time, until it finds the target or passes where it should have been. About √n jumps to find the right block, then up to √n steps to scan it, so the work grows like √n overall. That is slower than binary search’s O(log n), but jump search only ever moves forward. On storage where jumping backward is expensive, that one-directional access can be worth more than the better big-O.

Watch the shaded band leap across the array in even strides, then settle onto a single block and comb through it. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.