2019-05-10 17:43:44 +09:00
|
|
|
/* The Jump Search algorithm allows to combine a linear search with a speed optimization.
|
2023-10-03 23:08:19 +02:00
|
|
|
* 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.
|
2019-05-10 17:43:44 +09:00
|
|
|
*/
|
|
|
|
|
|
2019-05-11 10:13:32 +08:00
|
|
|
const jumpSearch = (arr, value) => {
|
2020-05-03 09:05:12 +02:00
|
|
|
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
|
2019-05-10 17:43:44 +09:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2019-05-11 10:13:32 +08:00
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
const upperBound = Math.min(step, length)
|
|
|
|
|
while (arr[lowerBound] < value) {
|
|
|
|
|
lowerBound++
|
|
|
|
|
if (lowerBound === upperBound) {
|
|
|
|
|
return -1
|
2019-05-11 10:13:32 +08:00
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
|
|
|
|
if (arr[lowerBound] === value) {
|
|
|
|
|
return lowerBound
|
|
|
|
|
}
|
|
|
|
|
return -1
|
2019-05-10 17:43:44 +09:00
|
|
|
}
|
2022-06-10 20:32:47 +05:30
|
|
|
|
|
|
|
|
export { jumpSearch }
|
