Jump Search in JavaScript
Just want the code? Scroll all the way down for two versions of the code:
- Without comments (just plug and use).
- With comments to have a better understanding of the code.
What is Jump Search?
Jump search is a search algorithm for sorted arrays. The concept is to search less elements than linear search by jumping ahead by a predetermined amount to find a block of elements where the target might be within. Once it finds the block the target is in, it’ll perform a linear search to search for the target.
Steps to Search using Jump Search
- Find a block size for the jump.
- Find the block that contains the target value.
- Perform Linear Search in the block the find the target.
Jump Search in JavaScript
Jump Search is a fairly simple search algorithm, the most complex part of the algorithm is determining how much to separate the blocks for the array. For this I simply use the root square of the array’s length. Feel free to write your own method to finding the steps if you wishes to.
Next we check with the end of each block to determine if the target value exist inside the block. We use Math.min to make sure we do not exceed the length of the array when checking with the last block.
Once we found the block that the value might exist, we use linear search from the beginning of the block to the end of the block.
Once we find the possible location for the target, compare it and if it doesn’t match, we know the element doesn’t exist within this array.
