Jump Search क्या है

Jump search एक किताब के कई pages एक साथ आगे skip करने जैसा है जब तक आप अपना page पार न कर जाएं, फिर पीछे step करके एक समय में एक page पढ़ना।

In this page:

What is Jump Search
Jump Size
Linear Scan
Complexity
Requirements and Uses

Syntax

markup

import math
step = int(math.sqrt(n))
prev = 0
while arr[min(step, n) - 1] < target:
    prev = step
    step += int(math.sqrt(n))
    if prev >= n:
        return -1
for i in range(prev, min(step, n)):
    if arr[i] == target:
        return i

What is Jump Search

Jump search sorted data पर हर element जांचने के बजाय fixed-size blocks में आगे skip करके काम करता है, तब तक आगे jump करते हुए जब तक यह एक block न ढूंढ ले जिसमें target हो सकता है, फिर सिर्फ उसी block के अंदर search करता है।

उदाहरण: What is Jump Search

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13,15,17,19}, n = 10, target = 13, step = 3, i = 0;
    while (i < n && arr[i] < target) i += step;
    cout << "Jumped to block starting at index " << i << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13,15,17,19};
        int target = 13, step = 3, i = 0;
        while (i < arr.length && arr[i] < target) i += step;
        System.out.println("Jumped to block starting at index " + i);
    }
}

arr = [1,3,5,7,9,11,13,15,17,19]
target, step, i = 13, 3, 0
while i < len(arr) and arr[i] < target:
    i += step
print("Jumped to block starting at index", i)

#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13,15,17,19}, n = 10, target = 13, step = 3, i = 0;
    while (i < n && arr[i] < target) i += step;
    printf("Jumped to block starting at index %d\n", i);
    return 0;
}

Jump Size

Typical block size array की length का square root है — यह specific size jumps की संख्या को final linear scan के size के खिलाफ balance करता है, worst case में total work minimize करते हुए।

उदाहरण: Jump Size

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n = 100;
    int blockSize = (int)sqrt(n);
    cout << "Optimal block size for n=" << n << " is " << blockSize << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int n = 100;
        int blockSize = (int) Math.sqrt(n);
        System.out.println("Optimal block size for n=" + n + " is " + blockSize);
    }
}

import math
n = 100
block_size = int(math.sqrt(n))
print("Optimal block size for n=", n, "is", block_size)

#include <stdio.h>
#include <math.h>
int main() {
    int n = 100;
    int blockSize = (int)sqrt((double)n);
    printf("Optimal block size for n=%d is %d\n", n, blockSize);
    return 0;
}

Linear Scan

एक बार एक block मिल जाए जहां target plausibly हो सकता है (block का आखिरी element target से बड़ा या बराबर हो), jump search exact position pinpoint करने के लिए उसी block के अंदर एक simple linear scan पर वापस आता है।

उदाहरण: Linear Scan

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 7, step = 3;
    int prev = 0, i = 0;
    while (i < 7 && arr[i] < target) { prev = i; i += step; }
    for (int j = prev; j < 7 && arr[j] <= target; j++)
        if (arr[j] == target) { cout << "Found at index " << j << endl; break; }
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,13};
        int target = 7, step = 3, prev = 0, i = 0;
        while (i < arr.length && arr[i] < target) { prev = i; i += step; }
        for (int j = prev; j < arr.length; j++)
            if (arr[j] == target) { System.out.println("Found at index " + j); break; }
    }
}

arr = [1,3,5,7,9,11,13]
target, step, prev, i = 7, 3, 0, 0
while i < len(arr) and arr[i] < target:
    prev = i
    i += step
for j in range(prev, len(arr)):
    if arr[j] == target:
        print("Found at index", j)
        break

#include <stdio.h>
int main() {
    int arr[] = {1,3,5,7,9,11,13}, target = 7, step = 3, prev = 0, i = 0;
    while (i < 7 && arr[i] < target) { prev = i; i += step; }
    for (int j = prev; j < 7; j++)
        if (arr[j] == target) { printf("Found at index %d\n", j); break; }
    return 0;
}

Complexity

Jump search worst case में लगभग O(√n) comparisons लेता है — binary search के O(log n) से धीमा लेकिन plain linear search के O(n) से तेज़, दोनों approaches के बीच एक middle ground में बैठते हुए।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
    cout << "Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search");
    }
}

print("Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search")

#include <stdio.h>
int main() {
    printf("Jump search: about O(sqrt n) comparisons -- slower than O(log n) binary search, faster than O(n) linear search\n");
    return 0;
}

Requirements and Uses

Jump search को sorted data चाहिए, binary search जैसा, और मुख्य रूप से तब उपयोगी है जब पीछे jump करना महंगा हो (जैसे कुछ storage media पर जहां sequential forward access random access से कहीं सस्ता है) — ordinary in-memory arrays में, binary search आमतौर पर बेहतर default है।

उदाहरण: Requirements and Uses

#include <iostream>
using namespace std;
int main() {
    cout << "Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)");
    }
}

print("Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)")

#include <stdio.h>
int main() {
    printf("Jump search requires sorted data; useful when backward seeks are expensive (e.g. tape storage)\n");
    return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Ternary Search Next Lesson → Binary Tree Introduction