Algorithm Guidecomplexity: O(√n)

점프 탐색 (Jump Search)

정렬된 배열을 √n 크기의 블록으로 점프하며 탐색 범위를 빠르게 좁힌 뒤, 후보 블록 내부에서 선형 탐색을 수행합니다. 이진 탐색보다 점프 비용은 크지만, 역방향 이동이 비싼 저장 매체(자기 테이프·디스크)에서 유리합니다.

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Jump Search

점프 탐색 시작. n=10, √n ≈ 3 이므로 step=3. √n 간격의 블록으로 뛰어넘으며 목표 45의 위치를 좁혀갑니다.

Logic Node1 / 6

Live Python

# target: 45

1def jump_search(arr, target):

# n: 10

2 n = len(arr)

# step: √10 ≈ 3

3 step = int(math.sqrt(n))

4 prev = 0

5 while arr[min(step, n) - 1] < target:

6 probe = arr[min(step, n) - 1]

7 prev = step

8 step += int(math.sqrt(n))

9 if prev >= n:

10 return -1

11 while arr[prev] < target:

12 prev += 1

13 if prev == min(step, n):

14 return -1

15 if arr[prev] == target:

16 return prev

17 return -1

02 Understand It Simply

For Everyone

🔑Analogy

계단을 √n칸씩 건너뛰며 대략 위치를 찾고, 그 구간만 천천히 보는 것.

💡In Plain Words

√n 크기로 점프해 후보 블록을 빠르게 찾은 뒤, 그 안에서 선형 탐색합니다.

역방향 이동이 비싼 매체에 유리해요.

📍Where It's Used

–정렬된 데이터
–순차 접근 매체(테이프·디스크)

03 Python Implementation

A clean, readable reference implementation of the core logic of 점프 탐색 (Jump Search).

core_implementation.py

import math

def jump_search(arr, target):
    n = len(arr)
    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
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    if arr[prev] == target:
        return prev
    return -1