JumpSearch.js

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