Day 9: Jump Search (Square Root Search)

1. Introduction

Jump Search is a searching algorithm for sorted arrays.
It works by jumping ahead by fixed steps (instead of checking every element like Linear Search) and then doing a Linear Search in a smaller block where the target might be.

It’s often faster than Linear Search but slower than Binary Search — and it’s useful when:

• You want a balance between simplicity and performance.

• Random access (direct index access) is possible.

---

2. How It Works

1. Determine a block size (commonly √n, where n is the number of elements).

2. Jump forward in steps of this block size until you either find the target or pass it.

3. Perform a Linear Search within the block where the target might be.

---

Example:
Array = [1, 3, 5, 7, 9, 11, 13, 15], target = 11

• Step size = √8 ≈ 2

• Check index 0 → 1

• Jump to index 2 → 5

• Jump to index 4 → 9

• Jump to index 6 → 13 (passed target)

• Linear search from index 4 to 6 → found 11.

---

3. Pseudocode

arduinoCopyEditfunction jumpSearch(arr, target):
    n = length of arr
    step = floor(sqrt(n))
    prev = 0

    while arr[min(step, n)-1] < target:
        prev = step
        step += floor(sqrt(n))
        if prev >= n:
            return -1

    while arr[prev] < target:
        prev++
        if prev == min(step, n):
            return -1

    if arr[prev] == target:
        return prev

    return -1

---

4. JavaScript Implementation

javascriptCopyEditfunction jumpSearch(arr, target) {
    const 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;
    }

    while (arr[prev] < target) {
        prev++;
        if (prev === Math.min(step, n)) return -1;
    }

    return arr[prev] === target ? prev : -1;
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(jumpSearch(arr, 11)); // Output: 5

---

5. Time Complexity

• Best case: O(1)

• Average case: O(√n)

• Worst case: O(√n)
  Space complexity: O(1) (in-place)

---

6. When to Use

• Works best when:

  • The array is sorted.

  • Random access to elements is possible (e.g., arrays, not linked lists).

  • You need faster performance than Linear Search but Binary Search isn’t possible (due to some constraints).

#CodeWithGift #DSA2025 #JavaScript #DayNine