Algorithm Guidecomplexity: O(√n)

점프 탐색 (Jump Search)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

Jump Search

목표45

step3

prev0

상태대기

점프 탐색 시작. 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 파이썬 구현 코드

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

Guide Progress0%