Algorithm Guidecomplexity: O(√n)

점프 탐색 (Jump Search)

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

01 알고리즘 작동 원리 탐색

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 쉽게 이해하기

For Everyone

🔑비유

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

💡쉽게 말하면

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

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

📍어디에 쓰나

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

03 파이썬 구현 코드

점프 탐색 (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