[Algorithm] 색인 순차 탐색 (Indexed Sequential Search)

1. 개요

색인 순차 탐색 은 순차 탐색 의 발전 형태로, 색인 배열 (Indexed Array) 의 형태의 구조로 저장된 자료에 대해 탐색하는 방식을 의미한다. 해당 방식은 완전 탐색이 이루어지지 않으므로 브루트 포스 의 범주에서 벗어난다.

2. 의의

순차 탐색 을 개선한 방식으로 더 효율적인 탐색이 가능하다는 의의가 있다.

3. 조건

색인 순차 탐색의 조건

1. 정렬된 배열
2. 추가 메모리 공간 (색인 배열)

4. 구현

색인 순차 탐색 알고리즘은 반드시 배열이 정렬되어 있어야 하며, 색인 배열를 활용할 추가적인 메모리 공간이 있어야 한다.

구현 절차는 다음을 따른다.

색인 순차 탐색의 절차

1. 색인 배열 크기 설정
2. 색인 배열 값 설정
3. 색인 배열에서 확인된 범위에 따른 배열 일부 탐색

먼저 다음을 정의한다.

• 배열: $A$
• 색인 배열: $I$
• 배열의 크기: $|A| = n$
• 색인 배열의 크기: $|I| = m$

4.1. 색인 배열 크기 설정

후술하겠지만 색인 순차 탐색 의 시간복잡도는 $O (m + {n \over m})$ 으로, 색인 배열의 크기 ($m$) 의 영향을 받는다.

이때, $n$ 은 상수로, $m + {n \over m}$ 의 값이 가질 수 있는 최솟값은 $\sqrt {n}$ 이다.

따라서 시간 효율을 극대화 할 수 있는 색인 배열의 크기는 $m = \lfloor{ \sqrt{ n } \ \rceil}$ 이다. 따라서 탐색할 배열의 크기의 제곱근과 가까운 정수를 색인 배열의 크기로 설정한다.

4.2. 색인 배열 값 설정

색인 배열의 크기를 설정했다면, 이제 값을 설정할 차례이다.

탐색할 배열 $A$ 을 $m$ 등분하여 각 부분의 첫 원소의 색인과 값의 순서쌍을 색인 배열에 저장한다.

$$
A = { a_0, a_1, ..., a_n } \\ \ I = { (0, a_0), (m, a_m), ..., (m (m - 1), a_{m (m - 1)}) }
$$

4.3. 색인 배열에서 확인된 범위에 따른 배열 일부 탐색

$s$ 값을 탐색한다고 할 때, 먼저 색인 배열 $I$ 에서 탐색할 범위를 설정한다.

배열 $I$ 의 $i$ 번째 원소는 $(mi, a_{ mi })$ 이다.
임의의 $i$ 에 대하여 $ a_{ mi } \le s \lt a_{ m(i + 1) }$ 를 만족한다면, 배열 $A$ 의 $[mi, m(i + 1))$ 범위에 해당하는 색인에 대한 탐색만 진행하면 된다.

5. 예시) 배열에서 값의 위치 찾기

선형 정수 배열(A)에서 특정 값(s)을 찾을 수 있으면 그 값의 색인(idx)를 출력하고, 배열에 값이 존재하지 않으면 -1 을 출력하는 코드를 작성해보자.

배열 $A$ 는 임의로 다음과 같이 설정하였다.

색인	0	1	2	3	4	5	6	7	8	9	10	11	12	13
$A$	$1$	$3$	$4$	$5$	$7$	$8$	$9$	$10$	$12$	$14$	$15$	$16$	$19$	$20$

# 탐색할 배열 (정렬 필요)
  A = [1, 3, 4, 5, 7, 8, 9, 10, 12, 14, 15, 16, 19, 20]
  
  # 탐색할 값
  s = int(input('s: '))
  
  def indexed_sequential_search(arr, s):
    n = len(arr)        # 탐색할 배열의 크기
    m = round(n ** .5)  # 색인 배열의 크기
  
    # 색인 배열
    I = [(i * m, arr[i * m]) for i in range(m)]
  
    # 탐색 범위
    rng = range(0)
  
    # 색인 배열 탐색
    for i in range(m):
      cur = I[i]
      nxt = (i == m - 1) * (n, arr[-1] + 1) or I[i + 1]
  
      if cur[1] <= s < nxt[1]:
        # 탐색 범위 설정
        rng = range(cur[0], nxt[0])
  
    idx = -1
  
    # 한정 범위에서의 탐색
    for i in rng:
      if arr[i] == s: idx = i
      if arr[i] >= s: break
  
    return idx
  
  print(indexed_sequential_search(A, s))

출력결과

s: 20
13

s: 2
-1

5.1. 색인 배열의 크기 설정

시간 효율을 극대화할 수 있도록 색인 배열의 값을 $m = \lfloor{ \sqrt{ n } \ \rceil}$ 으로 설정하였다.

m = round(n ** .5)

위 경우 임의 설정한 배열 $A$ 의 크기가 $n = 14$ 이므로, $m = \lfloor{ \sqrt{ 14 } \ \rceil} = 4$ 의 값을 갖게 된다.

5.2. 색인 배열 값 설정

색인 배열은 설정한 $m$ 값에 따라 다르게 설정된다.

I = [(i * m, arr[i * m]) for i in range(m)]

위 경우 $m = 4$ 이므로, 색인 배열은 다음과 같이 설정된다.

색인	0	1	2	3
$I$	$(0, 1)$	$(4, 7)$	$(8, 12)$	$(12, 19)$

5.3. 색인 배열에서 확인된 범위에 따른 배열 일부 탐색

5.3.1. 탐색값이 배열 $A$ 에 존재하는 경우

임의의 탐색값으로 $9$ 을 선택한다.

색인	0	1	2	3
$I$	$(0, 1)$	$(4, 7)$	$(8, 12)$	$(12, 19)$

$9$ 은 $7$ 이상 $12$ 미만이므로 배열 $I$ 의 색인 $1$ 의 범위에 해당하기 때문에 탐색 범위는 $[4, 8)$ 으로 줄어든다.

색인	0	1	2	3	4	5	6	7	8	9	10	11	12	13
$A$	$1$	$3$	$4$	$5$	$7$	$8$	$9$	$10$	$12$	$14$	$15$	$16$	$19$	$20$

위 표의 붉은색 부분이 탐색 범위에 해당하며 3번에 탐색 끝에 $6$ 번째에 탐색값 $9$ 이 존재함을 확인할 수 있다.

출력결과

s: 9
6

5.3.2. 탐색값이 배열 $A$ 에 존재하지 않는 경우

임의의 탐색값으로 $2$ 을 선택한다.

색인	0	1	2	3
$I$	$(0, 1)$	$(4, 7)$	$(8, 12)$	$(12, 19)$

$2$ 는 $1$ 이상 $7$ 미만이므로 배열 $I$ 의 색인 $0$ 의 범위에 해당하기 때문에 탐색 범위는 $[0, 4)$ 으로 줄어든다.

색인	0	1	2	3	4	5	6	7	8	9	10	11	12	13
$A$	$1$	$3$	$4$	$5$	$7$	$8$	$9$	$10$	$12$	$14$	$15$	$16$	$19$	$20$

위 표의 붉은색 부분이 탐색 범위에 해당하며 2번에 탐색 끝에 탐색값 $2$ 가 배열 $A$ 에 존재하지 않음이 확인되며, $-1$ 을 출력하고 종료된다.

출력결과

s: 2
-1

6. 시간복잡도

색인 순차 탐색 알고리즘은 색인 배열을 만드는 시간복잡도와, 실제 탐색을 수행하는 시간복잡도의 합으로 이루어진다. 이때, 색인 배열을 만드는 시간복잡도는 항상 $O (m)$ 이라 할 수 있다.

더불어 $m$ 값에 따라서도 시간복잡도가 달라지는데, $m = \sqrt{n}$ 일 때가 가장 시간 효율이 높다. $m$ 을 이처럼 설정했을 때와 그렇지 않을 때 시간복잡도가 어떻게 변화하는지도 살펴보자.

6.1. 최악 시간복잡도

실제 탐색을 수행하는데 걸릴 수 있는 최악의 시간복잡도는 $O ({ n \over m })$ 라고 할 수 있다.

따라서, $m = \sqrt{n}$ 일 때의 최악 시간복잡도는 다음과 같다.

$$
O (m) + O \left( { n \over m } \right) = O (\sqrt{n})
$$

한편 $m = n$ 으로 설정한다면, 최악 시간복잡도는 다음과 같아진다.

$$
O (n)
$$

6.2. 평균 시간복잡도

실제 탐색을 수행하는데 걸릴 수 있는 평균의 시간복잡도 역시 $O ({ n \over m })$ 라고 할 수 있다.

따라서, $m = \sqrt{n}$ 일 때의 평균 시간복잡도는 다음과 같다.

$$
\Theta ( m ) + \Theta \left( { n \over m } \right) = \Theta (\sqrt{n})
$$

6.3. 최선 시간복잡도

실제 탐색에서 바로 값을 찾는다면 $O (1)$ 의 시간복잡도를 갖는다.

따라서, $m = \sqrt{n}$ 일 때의 평균 시간복잡도는 다음과 같다.

$$
\Omega (m) + \Omega (1) = \Omega (\sqrt{n})
$$

6.4. 정리

• 탐색 한정

	최악	평균	최선
최적 $m$	$$ O (\sqrt{n}) $$	$$ \Theta (\sqrt{n}) $$	$$ \Omega (1) $$
임의 $m$	$$ O (n) $$	$$ \Theta \left( {n \over m} \right) $$	$$ \Omega (1) $$

• 색인 배열 생성 및 탐색

	최악	평균	최선
최적 $m$	$$ O (\sqrt{n}) $$	$$ \Theta (\sqrt{n}) $$	$$ \Omega (\sqrt{n}) $$
임의 $m$	$$ O (n) $$	$$ \Theta \left( m + {n \over m} \right) $$	$$ \Omega (\sqrt{n}) $$

7. 관련 알고리즘

7.1. 순차 탐색 (Indexed Sequential Search)

• [Algorithm] 순차 탐색 (Sequential Search)