Algorithm Guidecomplexity: O(√n)

점프 탐색 (Jump Search)

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

01점프 탐색 (Jump Search)

알고리즘 작동 원리 탐색

점프 탐색을 시작합니다. 값 열 개를 √n 인 세 칸씩 건너뛰며 목표 45가 있을 구간부터 찾습니다.

세 칸 뛴 자리의 값은 23으로 45보다 작습니다. 이 구간에는 없으니 다시 세 칸 뜁니다.

다음 자리의 값은 56 — 목표를 넘어섰습니다. 45가 있다면 방금 지나온 구간 안입니다.

지나온 구간을 앞에서부터 훑습니다. 첫 값 34는 목표가 아닙니다.

그다음 값이 45 — 목표와 일치합니다. 탐색을 종료합니다.

탐색 완료 · 45는 인덱스 4에 있습니다. 건너뛰기 세 번에 훑기 두 번, 모두 다섯 번만 비교했습니다.

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

1 / 6

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