JavaScript/Search/JumpSearch.js at master · TheAlgorithms/JavaScript · GitHub

33 lines (30 loc) · 977 Bytes

/* 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

}

export { jumpSearch }

Expand file tree