Jump Search is a searching algorithm designed to make searching through a sorted array faster than Linear Search while being simpler than Binary Search. Instead of checking every element one by one, Jump Search skips ahead by fixed steps, called “jumps,” and then performs a linear search within the identified block. This makes it an efficient and beginner-friendly algorithm for learning how to optimize search operations in TypeScript.
with hands-on learning.
get the skills and confidence to land your next move.
Jump Search is especially useful when working with large, sorted datasets where sequential searches would be slow. It finds a balance between simplicity and speed, making it ideal for beginners who are exploring different search algorithms. Understanding Jump Search helps you learn important concepts like step size calculation, block searching, and array traversal.
Program 1: Iterative Jump Search
This program demonstrates a standard Jump Search using iteration. It calculates an optimal jump size and searches through the array in blocks.
function jumpSearch(arr: number[], target: number): number {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
for (let i = prev; i < Math.min(step, n); i++) {
if (arr[i] === target) return i;
}
return -1;
}
let data: number[] = [1, 3, 5, 7, 9, 11, 13];
let targetValue: number = 9;
console.log("Element found at index:", jumpSearch(data, targetValue));In this program, the algorithm first jumps ahead in steps, then performs a linear search within the identified block. Beginners can see how breaking the search into blocks reduces comparisons compared to checking each element sequentially.
Program 2: Jump Search Using a While Loop
This version highlights Jump Search implemented purely with a while loop for clarity and simplicity.
function jumpSearchWhile(arr: number[], target: number): number {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (
prev < n &&
arr[Math.min(prev + step, n) - 1] < target
) {
prev += step;
}
let start = prev;
let end = Math.min(prev + step, n);
for (let i = start; i < end; i++) {
if (arr[i] === target) return i;
}
return -1;
}
let numbers: number[] = [2, 4, 6, 8, 10, 12, 14];
let searchValue: number = 10;
console.log("Element found at index:", jumpSearchWhile(numbers, searchValue));Using a while loop emphasizes the jumping mechanism and helps beginners understand how step size affects search efficiency.
Program 3: Recursive Jump Search
Jump Search can also be implemented recursively by dividing the search into blocks.
function jumpSearchRecursive(
arr: number[],
target: number,
step: number = Math.floor(Math.sqrt(arr.length)),
prev: number = 0
): number {
let end = Math.min(prev + step, arr.length);
if (end >= arr.length || arr[end - 1] >= target) {
for (let i = prev; i < end; i++) {
if (arr[i] === target) return i;
}
return -1;
}
return jumpSearchRecursive(arr, target, step, prev + step);
}
let values: number[] = [1, 5, 10, 15, 20, 25, 30];
let target: number = 15;
console.log("Element found at index:", jumpSearchRecursive(values, target));This recursive approach shows beginners how the jump and block search can be represented elegantly without loops. It also demonstrates how recursion can model real-world search strategies.
Program 4: Jump Search for Negative Numbers
Jump Search works with negative numbers as long as the array is sorted.
function jumpSearch(arr: number[], target: number): number {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
for (let i = prev; i < Math.min(step, n); i++) {
if (arr[i] === target) return i;
}
return -1;
}
let negatives: number[] = [-30, -20, -10, 0, 10, 20];
let targetNegative: number = -10;
console.log("Element found at index:", jumpSearch(negatives, targetNegative));Beginners can see that the algorithm handles negative values naturally because comparisons work the same way for negative numbers.
Program 5: Jump Search for Floating Point Numbers
Jump Search can also handle decimals in a sorted array.
function jumpSearch(arr: number[], target: number): number {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
for (let i = prev; i < Math.min(step, n); i++) {
if (arr[i] === target) return i;
}
return -1;
}
let decimals: number[] = [0.5, 1.0, 1.5, 2.0, 2.5, 3.0];
let targetDecimal: number = 2.0;
console.log("Element found at index:", jumpSearch(decimals, targetDecimal));This example demonstrates that Jump Search is versatile, working efficiently with floating point numbers in sorted datasets.
Program 6: Jump Search for Large Arrays
Jump Search is highly efficient for large arrays compared to Linear Search.
function jumpSearch(arr: number[], target: number): number {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
for (let i = prev; i < Math.min(step, n); i++) {
if (arr[i] === target) return i;
}
return -1;
}
let largeArray: number[] = Array.from({length: 1000}, (_, i) => i * 2);
let targetLarge: number = 600;
console.log("Element found at index:", jumpSearch(largeArray, targetLarge));Even with a thousand elements, the algorithm quickly locates the target using jumps, which is much faster than checking each element individually.
Program 7: Jump Search with Duplicate Values
This program shows how Jump Search handles arrays with repeated elements, returning the first occurrence it finds.
function jumpSearch(arr: number[], target: number): number {
let n = arr.length;
let step = Math.floor(Math.sqrt(n));
let prev = 0;
while (arr[Math.min(step, n) - 1] < target) {
prev = step;
step += Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
for (let i = prev; i < Math.min(step, n); i++) {
if (arr[i] === target) return i;
}
return -1;
}
let duplicates: number[] = [5, 10, 10, 15, 20, 20, 25];
let targetDuplicate: number = 20;
console.log("Element found at index:", jumpSearch(duplicates, targetDuplicate));Beginners can see that Jump Search efficiently locates a target even in arrays with duplicates, making it versatile for real-world data.
Frequently Asked Questions (FAQ)
Jump Search often raises common beginner questions:
Q1. Can Jump Search be used on unsorted arrays?
No, the array must be sorted for Jump Search to work correctly.
Q2. How is Jump Search different from Linear and Binary Search?
It combines ideas from both: it jumps ahead like a block search but performs linear search within blocks.
Q3. Can Jump Search handle negative and decimal numbers?
Yes, it works with any numerical values as long as the array is sorted.
Q4. How is the jump size calculated?
The optimal jump size is usually the square root of the array length, which balances jumps and linear search.
Q5. Is Jump Search efficient for large datasets?
Yes, it reduces comparisons significantly compared to Linear Search, especially in large, sorted arrays.
Conclusion
Jump Search is a simple yet efficient searching algorithm for sorted arrays. In this article, we explored TypeScript programs demonstrating Jump Search using iteration, recursion, negative numbers, decimals, duplicates, and large arrays. Each example highlighted how jumping in blocks and then performing a linear search improves efficiency while keeping the algorithm easy to understand for beginners.
By practicing these programs, beginners can understand how to balance simplicity and efficiency in search algorithms. Mastering Jump Search also provides a solid foundation for learning more advanced search techniques, helping you write faster and more optimized TypeScript code for real-world datasets.
![C++ Operator Overloading: The Array New Operator (new[])](https://coderscratchpad.com/wp-content/uploads/2024/05/Wordpress-blog-1200-x-600-px-8-2-1024x512.webp)
