jump Search Algorithm
The Jump Search Algorithm is an efficient searching technique that is applied to sorted arrays or lists. It is an improvement over the traditional Linear Search, which involves traversing through the whole list to find the desired element. Jump Search, as the name suggests, takes a "jump" instead of checking every element in the sequence. The basic idea behind this algorithm is to jump a fixed number of steps or elements, say 'm', at each iteration, and then perform a linear search between the elements where the desired value could potentially be located.
To determine the optimal value of 'm', the algorithm takes advantage of the fact that a sorted array has its elements in increasing or decreasing order. Generally, the value of 'm' is chosen to be the square root of the length of the array, as it is considered to be the most efficient choice. In each iteration, the algorithm compares the desired value with the element at the current jump position. If the desired value is found, the search is successful. If the desired value is greater than the current element, the algorithm jumps forward by 'm' positions. If the desired value is smaller than the current element, the algorithm performs a linear search within the previous 'm' positions. This combination of jumping and linear searching makes the Jump Search Algorithm faster than the Linear Search while still being relatively simple to understand and implement.
/* 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)
