Our FREE site is mostly funded by the Amazon ads ⇓below⇓.

Support us by clicking ⇑above⇑ next time you plan to buy a product on Amazon.

/* The Jump Search algorithm allows to combine a linear search with a speed optimization.
* This means that instead of going 1 by 1, we will increase the step of √n and increase that
* step of √n which make the step getting bigger and bigger.
* The asymptotic analysis of Jump Search is o(√n). Like the binary search, it needs to be sorted.
* The advantage against binary search is that Jump Search traversed back only once.
*/
const jumpSearch = (arr, value) => {
const length = arr.length;
let step = Math.floor(Math.sqrt(length));
let lowerBound = 0;
while (arr[Math.min(step, length) - 1] < value) {
lowerBound = step;
step += step;
if (lowerBound >= length) {
return -1;
}
}
const upperBound = Math.min(step, length);
while (arr[lowerBound] < value) {
lowerBound++;
if (lowerBound === upperBound) {
return -1;
}
}
if (arr[lowerBound] === value) {
return lowerBound;
}
return -1;
}
const arr = [0,0,4,7,10,23,34,40,55,68,77,90]
jumpSearch(arr,4);
jumpSearch(arr,34);
jumpSearch(arr,77);