Jump Search
Algorithm · Stretch
Step through it: Modified Binary Search pattern
target = 23
Step 1 of 6
Goal: find 23 in this sorted list. Checking one number at a time could take 7 looks, and a million numbers would take up to a million. Because the list is sorted, we can do far better.
Step 2 of 6
Look at the middle number first. The middle of positions 0 to 6 is position 3, which holds 12.
Step 3 of 6
12 is smaller than 23, and the list is sorted, so 23 cannot be at or before 12. Throw away that whole half. Only positions 4 to 6 are left.
Step 4 of 6
Do the same thing on what is left. The middle of positions 4 to 6 is position 5, which holds 23. Found it.
Step 5 of 6
Two looks instead of up to seven. Every look halves what is left, so a million numbers need only about 20 looks. Halving the search area each time is called binary search.
Step 6 of 6
Your turn. Pick a target and press Next to watch each look. Try 7: it is not in the list.
Complexity
Time Complexity
O(√n) - because we do search by blocks of size √n.
Like Binary Search, Jump Search (or Block Search) is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.
For example, suppose we have an array arr[] of size n and block (to be jumped)
of size m. Then we search at the indexes arr[0], arr[m], arr[2 * m], ..., arr[k * m] and
so on. Once we find the interval arr[k * m] < x < arr[(k+1) * m], we perform a
linear search operation from the index k * m to find the element x.
What is the optimal block size to be skipped?
In the worst case, we have to do n/m jumps and if the last checked value is
greater than the element to be searched for, we perform m - 1 comparisons more
for linear search. Therefore the total number of comparisons in the worst case
will be ((n/m) + m - 1). The value of the function ((n/m) + m - 1) will be
minimum when m = √n. Therefore, the best step size is m = √n.
Code
import Comparator from '../../../utils/comparator/Comparator';
/**
* Jump (block) search implementation.
*
* @param {*[]} sortedArray
* @param {*} seekElement
* @param {function(a, b)} [comparatorCallback]
* @return {number}
*/
export default function jumpSearch(sortedArray, seekElement, comparatorCallback) {
const comparator = new Comparator(comparatorCallback);
const arraySize = sortedArray.length;
if (!arraySize) {
// We can't find anything in empty array.
return -1;
}
// Calculate optimal jump size.
// Total number of comparisons in the worst case will be ((arraySize/jumpSize) + jumpSize - 1).
// The value of the function ((arraySize/jumpSize) + jumpSize - 1) will be minimum
// when jumpSize = √array.length.
const jumpSize = Math.floor(Math.sqrt(arraySize));
// Find the block where the seekElement belong to.
let blockStart = 0;
let blockEnd = jumpSize;
while (comparator.greaterThan(seekElement, sortedArray[Math.min(blockEnd, arraySize) - 1])) {
// Jump to the next block.
blockStart = blockEnd;
blockEnd += jumpSize;
// If our next block is out of array then we couldn't found the element.
if (blockStart > arraySize) {
return -1;
}
}
// Do linear search for seekElement in subarray starting from blockStart.
let currentIndex = blockStart;
while (currentIndex < Math.min(blockEnd, arraySize)) {
if (comparator.equal(sortedArray[currentIndex], seekElement)) {
return currentIndex;
}
currentIndex += 1;
}
return -1;
}References
Practice
Modified Binary Search
- Binary SearchEasy
- Search Insert PositionEasy
- Sqrt(x)Easy
- First Bad VersionEasy
- Valid Perfect SquareEasy
- Arranging CoinsEasy
- Search in Rotated Sorted ArrayMedium
- Find Minimum in Rotated Sorted ArrayMedium
- Find First and Last Position of Element in Sorted ArrayMedium
- Find Peak ElementMedium
- Search a 2D MatrixMedium
- Koko Eating BananasMedium
- Capacity To Ship Packages Within D DaysMedium
- Time Based Key-Value StoreMedium
- Single Element in a Sorted ArrayMedium
- Minimum Number of Days to Make m BouquetsMedium
- Median of Two Sorted ArraysHard
- Split Array Largest SumHard
- Find Minimum in Rotated Sorted Array IIHard
Spotted a mistake or something unclear? Report it on GitHub.