이진 검색 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

이진 검색 알고리즘은 정렬된 배열에서 특정 값의 위치를 찾는 효율적인 검색 알고리즘이다. 배열의 중간 요소를 목표 값과 비교하여, 목표 값이 작으면 배열의 앞쪽 절반, 크면 뒤쪽 절반에서 반복적으로 검색 범위를 좁혀나간다. 이 과정을 통해 각 단계마다 탐색 범위를 절반으로 줄여, 최악의 경우에도 로그 시간 안에 검색을 완료한다. 이진 검색은 선형 검색보다 빠르지만, 배열이 정렬되어 있어야 한다는 제약이 있다. 이진 탐색 트리, 해싱, 균등 이진 탐색, 지수 탐색, 보간 탐색 등 다양한 변형과 응용이 존재하며, C, C++, Java, Python 등 여러 프로그래밍 언어의 표준 라이브러리에서 지원된다.

더 읽어볼만한 페이지

2 - 이진법
이진법은 0과 1 두 개의 숫자를 사용하는 밑이 2인 위치 기수법으로, 컴퓨터 과학의 기초가 되었으며 현대 컴퓨터에서 데이터를 저장하고 처리하는 데 사용된다.
2 - 페어 스케이팅
페어 스케이팅은 두 선수가 함께 스케이팅하며 고난도 기술을 구사하는 피겨 스케이팅 종목으로, 쇼트 프로그램과 프리스케이팅으로 구성되며, 1908년 하계 올림픽에서 정식 종목으로 채택되었다.
검색 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.
검색 알고리즘 - 역색인
역색인은 단어와 해당 단어가 포함된 문서 간의 관계를 나타내는 자료 구조이며, 검색 엔진의 쿼리 속도를 최적화하는 데 사용된다.

이진 검색 알고리즘
알고리즘 개요
종류	탐색 알고리즘
자료 구조	배열
시간 복잡도 (최악)	O(log n)
시간 복잡도 (최선)	O(1)
시간 복잡도 (평균)	O(log n)
공간 복잡도	O(1)
최적	예
관련 명칭
영어	Binary search (BS)
다른 이름	이분 탐색 반분 탐색
설명
알고리즘 종류	정렬된 배열에서 목표 값의 위치를 찾는 탐색 알고리즘
활용 분야	유한 정렬 배열 탐색 연속 함수 값 탐색 (이분법)

2. 알고리즘

이진 검색은 정렬된 배열에서 작동하며, 배열의 중간에 있는 요소와 목표 값을 비교하는 것으로 시작한다. 목표 값이 요소와 일치하면 배열 내에서 해당 위치가 반환된다. 목표 값이 요소보다 작으면 배열의 하위 절반에서 검색이 계속되고, 목표 값이 요소보다 크면 배열의 상위 절반에서 검색이 계속된다. 이 과정을 통해 알고리즘은 각 반복에서 목표 값이 존재할 수 없는 절반을 제거한다.^[44]

정렬된 리스트나 배열에서 중앙값을 기준으로 검색 값과의 크기 관계를 통해 검색 범위를 좁혀 나간다. 중앙값의 오른쪽에 있는지, 왼쪽에 있는지를 판단하여 한쪽은 검색 대상에서 제외하는 방식이다.

크기 관계를 이용하므로 정렬되지 않은 리스트나 크기 관계가 정의되지 않은 요소에는 사용할 수 없다.

n개의 데이터가 있을 때 시간 복잡도는 $O(\log_2 n)$ 이다. 한 번 연산할 때마다 검색 대상 데이터가 n/2개씩 줄어드는 효과를 얻을 수 있다.

2. 1. 절차

이진 검색은 정렬된 배열에서 특정 값을 찾는 알고리즘이다. 배열의 중간 요소와 목표 값을 비교하여 목표 값이 중간 요소와 같으면 그 위치를 반환하고, 작으면 배열의 왼쪽 절반에서, 크면 오른쪽 절반에서 검색을 계속하는 방식으로 작동한다.

정렬된 n개 요소의 배열 A (A₀ ≤ A₁ ≤ A₂ ≤ ... ≤ A_n-1)와 대상 값 T가 주어졌을 때, 이진 검색을 사용하여 A에서 T의 인덱스를 찾는 절차는 다음과 같다.

1. L을 0, R을 n-1로 설정한다.

2. L > R이면 검색 실패로 종료한다.

3. m (중간 요소 위치)을 (L+R)/2의 바닥 값으로 설정한다.

4. A_m < T이면 L을 m+1로 설정하고 2단계로, A_m > T이면 R을 m-1로 설정하고 2단계로 이동한다.

5. A_m = T이면 m을 반환하고 검색을 종료한다.

이 절차는 변수 L과 R로 검색 경계를 추적하며, 의사 코드는 다음과 같다.

```

'''function''' 이진_검색(A, n, T) '''is'''

L := 0

R := n − 1

'''while''' L ≤ R '''do'''

m := floor((L + R) / 2)

'''if''' A[m] < T '''then'''

L := m + 1

'''else if''' A[m] > T '''then'''

R := m − 1

'''else''':

'''return''' m

'''return''' 실패

```

(L+R)/2의 천장 함수를 사용할 수도 있다.
예시 1: 25 찾기

위치	1	2	3	4	5	6	7	8	9	10
데이터	1	3	5	11	12	13	17	22	25	28

| 단계 | L | R | m | A[m] | 결과 |

|-----|------|------|------|-------|------------------------------------|

| 1 | 0 | 9 | 4 | 12 | n, n, n, n, N, ?, ?, ?, ?, ? |

| 2 | 5 | 9 | 7 | 22 | n, n, n, n, N, n, n, N, ?, ? |

| 3 | 8 | 9 | 8 | 25 | n, n, n, n, N, n, n, N, '''○''', n |
예시 2: 4 찾기

위치	1	2	3	4	5	6	7	8	9	10
데이터	1	3	5	11	12	13	17	22	25	28

| 단계 | L | R | m | A[m] | 결과 |

|-----|------|------|------|-------|------------------------------------|

| 1 | 0 | 9 | 4 | 12 | ?, ?, ?, ?, N, n, n, n, n, n |

| 2 | 0 | 3 | 1 | 3 | n, N, ?, ?, N, n, n, n, n, n |

| 3 | 2 | 3 | 2 | 5 | n, N, N, n, N, n, n, n, n, n |

2. 1. 1. 다른 절차

위 절차와 달리, 중간 요소(''m'')가 대상(''T'')과 같은지 매 반복마다 확인하지 않는 구현 방식도 있다. 이 방식은 요소가 하나 남았을 때(''L''=''R''일 때)만 검사를 수행하여 비교 루프를 더 빠르게 만들지만, 평균적으로 한 번의 반복이 더 필요하다.^[4] 헤르만 보텐브루흐는 1962년에 이 검사를 생략하는 첫 번째 구현을 발표했다.^[4]

실행 절차는 다음과 같다.

# ''L''을 0으로, ''R''을 ''n''-1로 설정한다.

# ''L'' ≠ ''R''인 동안,

## ''m''(중간 요소의 위치)을 (''L''+''R'')/2의 천장 값으로 설정한다. 즉, (''L''+''R'')/2보다 크거나 같은 최소 정수이다.

## 만약 ''A_m'' > ''T''이면, ''R''을 ''m''-1로 설정한다.

## 그렇지 않으면, ''A_m'' ≤ ''T''이므로, ''L''을 ''m''으로 설정한다.

# 이제 ''L''=''R''이므로, 검색이 완료되었다. 만약 ''A_L''=''T''이면, ''L''을 반환한다. 그렇지 않으면 검색이 실패로 종료된다.

2. 2. 중복 요소

이진 검색 알고리즘은 배열에 중복된 요소가 있어도 대상 값과 동일한 요소를 가진 모든 인덱스를 반환할 수 있다. 예를 들어 배열이 [1, 2, 3, 4, 4, 5, 6, 7]이고 대상 값이 4인 경우, 알고리즘은 네 번째(인덱스 3) 또는 다섯 번째(인덱스 4) 요소를 반환할 수 있다. 일반적인 절차는 이 경우 네 번째 요소를 반환하지만, 항상 첫 번째 중복을 반환하는 것은 아니다.

배열에서 중복된 대상 값에 대해 가장 왼쪽 요소나 가장 오른쪽 요소를 찾아야 하는 경우가 있다. 예를 들어 위의 배열에서 네 번째 요소는 값 4의 가장 왼쪽 요소이고, 다섯 번째 요소는 값 4의 가장 오른쪽 요소이다.

다음은 정렬된 배열에서 특정 값을 찾는 예시이다. 배열 내에 값의 중복은 없다고 가정한다.

위치	1	2	3	4	5	6	7	8	9	10
데이터	1	3	5	11	12	13	17	22	25	28

위 배열에서 29를 찾는 경우, 배열의 가장 오른쪽 값이 29보다 작으므로, 데이터를 찾을 수 없다는 결과가 나온다.

2. 2. 1. 가장 왼쪽 요소를 찾는 절차

가장 왼쪽 요소를 찾기 위해 다음 절차를 사용할 수 있다.^[1]

# ''L''을 0으로, ''R''을 ''n''으로 설정한다.

# ''L'' < ''R''인 동안,

## ''m''(중간 요소의 위치)을

\frac{L+R}{2}

의 바닥 값으로 설정한다. 즉,

\frac{L+R}{2}

보다 작거나 같은 가장 큰 정수이다.

## 만약

A_m < T

이면, ''L''을 ''m''+1로 설정한다.

## 그렇지 않으면,

A_m \geq T

이므로 ''R''을 ''m''으로 설정한다.

# ''L''을 반환한다.

만약 ''L'' < ''n''이고

A_L = T

이면,

A_L

은 ''T''와 같은 가장 왼쪽 요소이다. ''T''가 배열에 없더라도, ''L''은 배열에서 ''T''의 순위이거나, ''T''보다 작은 배열 요소의 수이다.

위 절차를 의사 코드로 표현하면 다음과 같다.

```

function binary_search_leftmost(A, n, T):

L := 0

R := n

while L < R:

m := floor((L + R) / 2)

if A[m] < T:

L := m + 1

else:

R := m

return L

2. 2. 2. 가장 오른쪽 요소를 찾는 절차

오른쪽 끝 요소를 찾기 위한 절차는 다음과 같다.^[1]

# ''L''을 0으로, ''R''을 ''n''으로 설정한다.

# ''L'' < ''R''인 동안,

## ''m'' (중간 요소의 위치)을

\frac{L+R}{2}

의 바닥 함수 값(

\frac{L+R}{2}

보다 작거나 같은 가장 큰 정수)으로 설정한다.

##

A_m > T

이면, ''R''을 ''m''으로 설정한다.

## 그렇지 않으면 (

A_m \leq T

이면), ''L''을 ''m''+1로 설정한다.

# ''R'' - 1을 반환한다.

''R'' > 0이고

A_{R-1}=T

이면,

A_{R-1}

은 ''T''와 같은 가장 오른쪽에 있는 요소이다. ''T''가 배열에 없더라도, ''n''-''R''은 배열에서 ''T''보다 큰 요소의 수이다.

2. 3. 근사 일치

이진 검색은 근사 일치를 계산하도록 조정할 수 있습니다. 위의 예에서 대상 값 $5$ (배열에 없음)에 대한 순위, 선행자, 후속자 및 가장 가까운 이웃이 표시됩니다.

이진 검색은 대상 값의 위치를 찾는 '정확한' 일치뿐만 아니라, 정렬된 배열에서 작동하기 때문에 근사 일치를 수행하도록 확장할 수 있다. 예를 들어 이진 검색은 주어진 값에 대해 순위(더 작은 요소의 수), 선행자(다음으로 작은 요소), 후속자(다음으로 큰 요소) 및 가장 가까운 이웃을 계산하는 데 사용될 수 있다. 두 값 사이의 요소 수를 찾는 범위 쿼리는 두 개의 순위 쿼리로 수행할 수 있다.^[1]

순위 쿼리는 가장 왼쪽 요소를 찾는 절차를 사용하여 수행할 수 있다. 대상 값 ''미만''의 요소 수가 절차에 의해 반환된다.^[1]
선행자 쿼리는 순위 쿼리로 수행할 수 있다. 대상 값의 순위가 $r$ 이면, 선행자는 $r-1$ 이다.
후속자 쿼리의 경우 가장 오른쪽 요소를 찾는 절차를 사용할 수 있다. 대상 값에 대해 절차를 실행한 결과가 '' $r$ ''이면, 대상 값의 후속자는 $r+1$ 이다.
대상 값의 가장 가까운 이웃은 선행자 또는 후속자 중 더 가까운 것이다.
범위 쿼리도 간단하다. 두 값의 순위가 알려지면, 첫 번째 값보다 크거나 같고 두 번째 값보다 작은 요소의 수는 두 순위의 차이이다. 이 수는 범위의 끝점이 범위의 일부로 간주되어야 하는지 여부와 배열에 해당 끝점과 일치하는 항목이 포함되어 있는지 여부에 따라 1씩 위 또는 아래로 조정될 수 있다.^[1]

3. 성능

이진 검색의 성능은 비교 횟수를 기준으로 분석할 수 있으며, 이는 이진 트리를 통해 시각적으로 표현할 수 있다. 트리의 루트 노드는 배열의 중간 요소에 해당하며, 하위 절반의 중간 요소는 루트의 왼쪽 자식, 상위 절반의 중간 요소는 오른쪽 자식 노드가 되는 방식으로 트리가 구성된다.^[3]

이진 검색을 나타내는 트리. 여기서 검색되는 배열은 [20, 30, 40, 50, 80, 90, 100]이고, 대상 값은 40이다.

최악의 경우는 검색이 트리의 가장 깊은 레벨에 도달했을 때 발생하며, 최선의 경우는 대상 값이 중간 요소일 때 발생한다.

최악의 경우, 이진 검색은 ⌊log₂(n) + 1⌋ 번의 비교를 수행한다. 여기서 ⌊ ⌋는 바닥 함수를, log₂는 이진 로그를 나타내며, n은 배열의 요소 개수이다. 이는 검색이 트리의 가장 깊은 레벨에 도달하거나 대상 요소가 배열에 없을 때 발생한다.

평균적으로 대상 요소가 배열에 있을 때 이진 검색은 약 log₂(n) - 1번의 비교를 수행하고, 없을 때는 약 ⌊log₂(n)⌋ + 2 - 2⌊log₂(n)⌋ + 1 / (n + 1) 번의 비교를 수행한다. 최선의 경우, 대상 값이 배열의 중간 요소라면 한 번의 비교 후에 해당 위치가 반환된다.^[5]

반복 횟수만 고려했을 때, 요소를 비교하는 방식의 검색 알고리즘 중 이진 검색보다 평균 및 최악의 경우 성능이 더 뛰어난 알고리즘은 없다. 이진 검색 트리는 가장 낮은 레벨 위의 모든 레벨이 완전히 채워져 있어 가능한 가장 적은 레벨을 갖기 때문이다.

이진 검색은 비교를 통한 탐색에 최적의 알고리즘이며, n개의 노드를 가진 모든 이진 트리의 최소 내부 경로 길이는 다음과 같이 계산된다.

:math:`I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2`

실패한 검색의 경우, 평균 반복 횟수는 다음과 같다.

:math:`T'(n) = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)`

이진 검색 알고리즘의 각 반복은 평균 1.5회의 비교를 수행한다. 알고리즘의 한 변형은 검색이 끝날 때 중간 요소와 대상을 비교하여 평균적으로 각 반복에서 0.5회의 비교를 줄이지만, 매우 큰 n이 아니라면 추가 반복을 보상하지 못한다.^[5]

두 요소를 비교하는 데 걸리는 시간 또한 성능에 영향을 미친다. 정수나 문자열의 경우, 인코딩 길이(비트 수)가 증가하면 비교 시간도 선형적으로 증가한다. 부동 소수점 값을 비교하는 것은 정수나 짧은 문자열을 비교하는 것보다 더 많은 비용이 들 수 있다.

대부분의 컴퓨터에서 프로세서는 RAM과 별개로 캐시를 가진다. 캐시는 프로세서 내부에 있어 접근이 빠르지만, RAM보다 저장 용량이 작다. 이진 검색은 큰 배열에서 멀리 떨어진 메모리 위치로 이동할 수 있어, 참조 지역성에 따라 실행 시간에 영향을 줄 수 있다.^[6]

3. 1. 공간 복잡도

이진 검색은 배열의 크기에 관계없이 배열 인덱스 또는 메모리 위치에 대한 포인터일 수 있는 세 개의 요소에 대한 포인터를 필요로 한다. 따라서 이진 검색의 공간 복잡도는 워드 램 계산 모델에서

O(1)

이다.^[44]

4. 이진 탐색과 다른 방법의 비교

이진 탐색은 비교를 통한 탐색에 있어 최적의 알고리즘이다. 이진 탐색은 $n$ 개의 노드를 가진 이진 트리에서 최소 내부 경로 길이를 계산하는 방식으로 동작하며, 그 길이는 $I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor$ 로 표현된다.^[44] 예를 들어, 7개의 요소가 있는 배열에서 루트는 1번, 그 아래 두 요소는 2번, 나머지 네 요소는 3번의 반복을 거친다. 이때 내부 경로 길이는 $\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 10$ 이다.^[44]

평균 반복 횟수는 $1 + \frac{10}{7} = 2 \frac{3}{7}$ 이며, 이는 $T(n) = 1 + \frac{I(n)}{n}$ 공식으로 계산된다. $I(n)$ 은 $I(n) = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2$ 로 단순화할 수 있다.^[44]

실패한 검색의 경우, 외부 노드를 추가하여 확장된 이진 트리를 구성한다. 외부 경로 길이는 $E(n) = I(n) + 2n$ 으로, 평균 반복 횟수는 $T'(n)=\frac{E(n)}{n+1}$ 이다. $E(n)$ 에 대한 방정식을 $T'(n)$ 에 대입하면, 실패한 검색에 대한 평균은 $T'(n) = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)$ 로 계산된다.^[44]

정렬된 배열에서 이진 검색을 사용하면 삽입 및 삭제에 $O(n)$ 시간이 소요되어 비효율적이다. 특히 요소가 자주 삽입될 때 메모리 사용이 복잡해진다.^[44] 따라서 더 효율적인 삽입 및 삭제를 지원하는 다른 자료 구조들이 존재한다. 이진 검색은 정확한 일치 및 집합 멤버십을 수행할 수 있지만, 더 빠른 자료 구조도 있다. 그러나 이진 검색은 효율적인 근사 일치를 $O(\log n)$ 시간에 수행할 수 있다는 장점이 있다.^[7] 또한, 정렬된 배열에서 가장 작거나 큰 요소를 찾는 연산도 효율적으로 수행할 수 있다.^[7]

4. 1. 선형 탐색

선형 검색은 찾고자 하는 값이 나올 때까지 모든 자료를 확인하는 간단한 검색 알고리즘이다. 선형 검색은 연결 리스트에서 수행할 수 있으며, 이는 배열보다 삽입 및 삭제가 더 빠르다. 이진 검색은 배열이 짧은 경우를 제외하고는 정렬된 배열에서 선형 검색보다 빠르지만, 배열을 미리 정렬해야 한다.^[44] 선형 검색과 달리 이진 검색은 효율적인 근사 매칭에 사용할 수 있다.

4. 2. 트리

이진 탐색 트리는 이진 탐색의 원리를 기반으로 작동하는 이진 트리 자료 구조이다. 트리의 레코드는 정렬된 순서로 배열되며, 각 레코드는 이진 탐색과 유사한 알고리즘을 사용하여 검색할 수 있어 평균적으로 대수 시간(logarithmic time)이 소요된다. 삽입 및 삭제 또한 평균적으로 대수 시간이 소요되는데, 이는 정렬된 배열의 선형 시간 삽입 및 삭제보다 빠를 수 있다. 이진 트리는 범위 및 근사 쿼리를 포함하여 정렬된 배열에서 가능한 모든 연산을 수행할 수 있는 기능을 유지한다.^[7]

그러나 이진 탐색 트리는 불완전하게 균형을 이루는 경우가 많아, 일반적으로 이진 탐색이 검색에 더 효율적이므로 이진 탐색보다 약간 성능이 떨어진다. 이는 자체 노드의 균형을 유지하는 균형 이진 탐색 트리에도 적용된다. 균형 이진 탐색 트리는 가능한 가장 적은 레벨의 트리를 거의 생성하지 않기 때문이다. 균형 이진 탐색 트리를 제외하면, 트리는 두 개의 자식을 가진 내부 노드가 거의 없어 심하게 불균형을 이룰 수 있으며, 그 결과 평균 및 최악의 경우 검색 시간이 n 번의 비교에 근접하게 된다. 이진 탐색 트리는 정렬된 배열보다 더 많은 공간을 차지한다.

이진 탐색 트리는 하드 디스크에 저장된 외부 메모리에서 빠른 검색에 적합하며, 파일 시스템에서 효율적으로 구조화될 수 있다. B-tree는 이러한 트리 구성 방식을 일반화한 것이다. B-트리는 데이터베이스 및 파일 시스템과 같은 장기 저장소의 구성에 자주 사용된다.

4. 3. 해싱

해시 테이블은 해시 함수를 사용하여 키를 레코드에 매핑하는 자료 구조로, 연관 배열을 구현하는 데 사용되며 정렬된 레코드 배열에서의 이진 검색보다 일반적으로 더 빠르다.^[6] 대부분의 해시 테이블 구현은 평균적으로 분할 상환 상수 시간만을 필요로 한다.^[8] 그러나 해싱은 다음으로 작은 키, 다음으로 큰 키 및 가장 가까운 키를 계산하는 것과 같은 근사 일치에는 유용하지 않다.^[9] 검색 실패 시 제공되는 유일한 정보는 대상이 어떤 레코드에도 존재하지 않는다는 것이다.^[9]

4. 4. 집합 멤버십 알고리즘

검색과 관련된 문제는 집합 멤버십이다. 이진 검색과 같은 조회 알고리즘은 집합 멤버십에도 사용할 수 있다. 집합 멤버십에 더 특화된 다른 알고리즘도 있다. 비트 배열은 가장 간단하며, 키의 범위가 제한적일 때 유용하다. 비트 배열은 비트의 모음을 콤팩트하게 저장하며, 각 비트는 키 범위 내의 단일 키를 나타낸다. 비트 배열은 매우 빠르며,

O(1)

시간만 필요하다. 주디 배열의 Judy1 유형은 64비트 키를 효율적으로 처리한다.^[10]

근사 결과를 위해, 해싱을 기반으로 하는 또 다른 확률적 자료 구조인 블룸 필터는 비트 배열과 여러 해시 함수를 사용하여 키를 인코딩하여 키의 집합을 저장한다. 블룸 필터는 대부분의 경우 비트 배열보다 훨씬 공간 효율적이며 속도도 크게 느리지 않다.

k

개의 해시 함수를 사용하면 멤버십 쿼리에

O(k)

시간만 필요하다. 그러나 블룸 필터는 가양성의 영향을 받는다.^[11]^[12]

4. 5. 기타 자료 구조

반 엠데 보아스 트리, 퓨전 트리, 트라이와 같은 특수 자료 구조는 특정 조건에서 검색, 근사 일치 및 정렬된 배열에 사용 가능한 연산들을 이진 검색보다 더 효율적으로 수행할 수 있다.^[7] 이러한 자료 구조는 일반적으로 작은 정수인 키의 속성을 활용하기 때문에 더 빠르지만, 해당 속성이 없는 키에 대해서는 시간이나 공간을 많이 소모할 수 있다.^[7] 주디 배열과 같은 일부 구조는 여러 방식을 조합하여 효율성을 유지하면서 근사 일치를 수행할 수 있도록 한다.^[10]

5. 변형

이진 검색은 정렬된 리스트나 배열에서 특정 값을 효율적으로 찾는 알고리즘이다. 중앙값을 기준으로 검색 범위를 절반씩 줄여나가기 때문에, 정렬되지 않은 리스트나 크기 비교가 불가능한 경우에는 사용할 수 없다. 이진 검색의 시간 복잡도는 $O(\log_2 n)$ 이다.^[44]

이진 검색은 한 번 비교할 때마다 검색 범위를 절반으로 줄인다. 중앙값을 찾아 검색하려는 값과 비교하여, 검색하려는 값이 중앙값보다 크면 오른쪽 절반을, 작으면 왼쪽 절반을 탐색하는 방식이다.

다음은 이진 검색의 주요 변형 알고리즘들이다.

균등 이진 탐색 (Uniform Binary Search): 중간 값의 위치 변화를 미리 계산하여 저장해 둠으로써, 중간 값 계산 과정을 줄여 탐색 속도를 높인다. 특히 십진 컴퓨터와 같이 중간점 계산이 느린 시스템에서 유용하다.^[1]
지수 탐색 (Exponential Search): 검색 범위를 빠르게 좁혀나가면서 이진 탐색을 적용할 상한값을 찾는다. 대상 값이 배열의 앞부분에 있을 때 특히 효과적이다.
보간 탐색 (Interpolation Search): 선형 보간법을 사용하여 대상 값의 위치를 예측한다. 데이터가 균등하게 분포되어 있을 때 매우 효율적이지만, 그렇지 않은 경우에는 이진 탐색보다 느릴 수 있다.^[13]
분할 캐스케이딩 (Fractional Cascading): 여러 개의 정렬된 배열에서 동시에 검색을 수행할 때 효율적이다. 각 배열의 요소를 서로 연결하여 중복 검색을 줄인다.^[14]^[15]
그래프로의 일반화: 이진 탐색 트리처럼 특정 유형의 그래프에서도 이진 검색을 적용할 수 있다.
노이즈 이진 탐색 (Noisy Binary Search): 비교 결과에 오류가 있을 수 있는 상황에서 사용된다. 오류 확률을 고려하여 대상 값의 위치를 찾는다.^[17]^[18]^[19]
양자 이진 탐색 (Quantum Binary Search): 양자 컴퓨터를 이용하여 이진 검색의 속도를 더욱 높일 수 있다.

5. 1. 균등 이진 탐색 (Uniform Binary Search)

균등 이진 검색은 특정 경계 대신 현재 중간 요소와 다음 두 개의 가능한 중간 요소 간의 차이를 저장합니다.

균등 이진 검색은 하한 및 상한 대신, 현재 반복에서 다음 반복으로 중간 요소의 인덱스 차이를 저장한다. 차이점을 포함하는 룩업 테이블이 사전에 계산된다. 예를 들어, 검색할 배열이 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]인 경우 중간 요소(''m'')는 6이 된다. 이 경우 왼쪽 하위 배열([1, 2, 3, 4, 5])의 중간 요소는 3이고 오른쪽 하위 배열([7, 8, 9, 10, 11])의 중간 요소는 9이다. 균등 이진 검색은 3의 값을 저장하는데, 이는 두 인덱스 모두 이 동일한 양만큼 6과 다르기 때문이다.^[1] 검색 공간을 줄이기 위해 알고리즘은 중간 요소의 인덱스에서 이 변경 사항을 더하거나 뺀다. 균등 이진 검색은 십진 컴퓨터와 같이 중간점을 계산하는 것이 비효율적인 시스템에서 더 빠를 수 있다.^[1]

5. 2. 지수 탐색 (Exponential Search)

지수 탐색은 이진 탐색을 무제한 목록으로 확장한 것이다. 지수 탐색은 먼저 대상 값보다 크고 2의 거듭제곱인 인덱스를 가진 첫 번째 요소를 찾는다. 그 후 해당 인덱스를 상한으로 설정하고 이진 탐색으로 전환한다. 탐색은 이진 탐색이 시작되기 전에

\lfloor \log_2 x + 1\rfloor

번 반복하고, 이진 탐색은 최대

\lfloor \log_2 x \rfloor

번 반복한다. 여기서

x

는 대상 값의 위치이다. 지수 탐색은 제한된 목록에서도 작동하지만, 대상 값이 배열의 시작 부분 근처에 있는 경우에만 이진 탐색보다 개선된다.

5. 3. 보간 탐색 (Interpolation Search)

선형 보간을 사용한 보간 검색의 시각화. 이 경우 배열 내의 대상 위치 추정이 정확하므로 검색이 필요하지 않습니다. 다른 구현에서는 대상 위치를 추정하기 위해 다른 함수를 지정할 수 있습니다.

보간 탐색은 중간점을 계산하는 대신 배열의 최저 및 최고 요소와 배열의 길이를 고려하여 대상 값의 위치를 추정한다. 이는 중간점이 많은 경우 최선의 추측이 아니라는 것을 기반으로 작동한다. 예를 들어, 대상 값이 배열의 최고 요소에 가까우면 배열의 끝 근처에 위치할 가능성이 높다.^[13]

일반적인 보간 함수는 선형 보간이다. A가 배열이고, L, R이 각각 하한 및 상한이며, T가 대상인 경우, 대상은 L과 R 사이의 약 (T - A_L) / (A_R - A_L) 지점에 있을 것으로 추정된다. 선형 보간이 사용되고 배열 요소의 분포가 균일하거나 거의 균일한 경우 보간 탐색은 O(log log n)번의 비교를 수행한다.^[13]

실제로 보간 탐색은 작은 배열의 경우 이진 검색보다 느리다. 보간 탐색은 추가 계산이 필요하기 때문이다. 시간 복잡성은 이진 검색보다 느리게 증가하지만, 이는 큰 배열의 추가 계산을 보상할 뿐이다.^[13]

5. 4. 분할 캐스케이딩 (Fractional Cascading)

분할 캐스케이딩에서 각 배열은 다른 배열의 모든 두 번째 요소에 대한 포인터를 가지므로 모든 배열을 검색하기 위해 하나의 이진 검색만 수행하면 된다.

분할 캐스케이딩은 여러 정렬된 배열에서 동일한 요소에 대한 이진 검색 속도를 높이는 기술이다. 각 배열을 개별적으로 검색하려면

O(k \log n)

시간이 필요하며, 여기서

k

는 배열의 수이다. 분할 캐스케이딩은 각 배열에 각 요소와 다른 배열에서의 위치에 대한 특정 정보를 저장하여 이를

O(k + \log n)

로 줄인다.^[14]^[15]

분할 캐스케이딩은 원래 다양한 계산 기하학 문제를 효율적으로 해결하기 위해 개발되었다. 데이터 마이닝 및 인터넷 프로토콜 라우팅과 같은 다른 곳에도 적용되었다.^[14]

5. 5. 그래프로의 일반화

이진 검색은 대상 값이 배열 요소 대신 정점에 저장되는 특정 유형의 그래프에서 작동하도록 일반화될 수 있다. 이진 탐색 트리는 그러한 일반화 중 하나이다. 트리의 정점(노드)을 질의하면 알고리즘은 해당 정점이 대상임을 알게 되거나, 그렇지 않으면 대상이 위치할 하위 트리를 알게 된다. 그러나 이것은 더 일반화될 수 있다. 무방향성, 양의 가중치를 갖는 그래프와 대상 정점이 주어지면, 알고리즘은 정점을 질의할 때 해당 정점이 대상과 같다는 것을 알게 되거나 질의된 정점에서 대상까지의 최단 경로에 있는 인접 간선을 얻게 된다. 표준 이진 검색 알고리즘은 그래프가 경로인 경우이다. 마찬가지로 이진 검색 트리는 질의된 정점이 대상과 같지 않을 때 왼쪽 또는 오른쪽 하위 트리에 대한 간선이 주어지는 경우이다. 모든 무방향성, 양의 가중치를 갖는 그래프에 대해 최악의 경우

O(\log n)

질의 내에 대상 정점을 찾는 알고리즘이 있다.

5. 6. 노이즈 이진 탐색 (Noisy Binary Search)

노이즈 이진 검색 알고리즘은 배열의 요소를 신뢰성 있게 비교할 수 없는 경우를 해결한다. 각 요소 쌍에 대해 알고리즘이 잘못된 비교를 할 특정 확률이 존재한다. 노이즈 이진 검색은 결과로 나오는 위치의 신뢰성을 제어하는 주어진 확률로 목표의 정확한 위치를 찾을 수 있다. 모든 노이즈 이진 검색 절차는 평균적으로 최소

(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}

번의 비교를 수행해야 한다. 여기서

H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)

는 이진 엔트로피 함수이고,

\tau

는 절차가 잘못된 위치를 산출할 확률이다.^[17]^[18]^[19] 노이즈 이진 검색 문제는 답변이 잘못될 수 있는 스무고개의 변형인 레니-울람 게임^[20]^[21]의 경우로 간주할 수 있다.

5. 7. 양자 이진 탐색 (Quantum Binary Search)

고전 컴퓨터에서 이진 검색은 최악의 경우

\lfloor \log_2 n + 1 \rfloor

번의 반복으로 제한된다. 양자 알고리즘을 사용한 이진 검색은 여전히

\log_2 n

쿼리(고전적인 방식의 반복) 비율로 제한되지만, 상수 인자가 1보다 작아 양자 컴퓨터에서 더 낮은 시간 복잡도를 가진다. 항상 올바른 결과를 생성하는 정확한 양자 이진 검색 절차는 최악의 경우 최소

\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n

쿼리가 필요하며, 여기서

\ln

는 자연 로그이다.^[22] 최악의 경우

4 \log_{605} n \approx 0.433 \log_2 n

쿼리로 실행되는 정확한 양자 이진 검색 절차도 있다.^[23] 그로버 알고리즘은 정렬되지 않은 요소 목록을 검색하기 위한 최적의 양자 알고리즘이며,

O(\sqrt{n})

쿼리가 필요하다.^[24]

6. 구현 상의 실수

도널드 커누스는 "이진 검색의 기본 아이디어는 비교적 간단하지만, 그 세부 사항은 놀랍도록 다루기 어려울 수 있다..."라고 말하며^[45], 이진 검색이 정확하게 구현되지 않는 경우가 많다고 지적했다. 흔한 실수 중 하나는 중간 위치를 계산할 때 `imin + (imax - imin) / 2` 대신 `(imax + imin) / 2`를 사용하여 정수 오버플로우를 유발하는 것이다. `(imax + imin) / 2`는 `imax + imin`이 int 값의 최댓값(INT_MAX)을 초과하여 부정확한 값이 될 가능성이 있다.^[47] Java의 표준 라이브러리 `Arrays.binarySearch()`에도 오랫동안 이 버그가 존재했다.^[47]

7. 코드 예시

C, C++, Python, Java 등 다양한 프로그래밍 언어로 이진 검색 알고리즘을 구현할 수 있다.

```c

// 재귀 함수를 사용한 이진 검색

BinarySearch(A[0..N-1], value, low, high) {

if (high < low)

return -1 // 값을 찾지 못함

mid = (low + high) / 2

if (A[mid] > value)

return BinarySearch(A, value, low, mid-1)

else if (A[mid] < value)

return BinarySearch(A, value, mid+1, high)

else

return mid // 값을 찾음

}

```

```c

// 반복문을 사용한 이진 검색

binarySearch(A[0..N-1], value) {

low = 0

high = N - 1

while (low <= high) {

mid = (low + high) / 2

if (A[mid] > value)

high = mid - 1

else if (A[mid] < value)

low = mid + 1

else

return mid // 값을 찾음

}

return -1 // 값을 찾지 못함

}

```

```cpp

// 반복문 버전 : A[0 ~ N-1]

int binarySearch(int A[], int low, int high, int target){

while(low <= high){

int mid = (low + high) / 2;

if(A[mid] == target) return mid;

if(A[mid] > target) high = mid - 1;

else low = mid + 1;

}

return -1;

}

// 재귀 버전 : A[0 ~ N-1]

int binarySearchRecur(int A[], int low, int high, int target){

if(low > high) return -1;

int mid = (low + high) / 2;

if(A[mid] == target) return mid;

if(A[mid] > target){

return binarySearchRecur(A, low, mid-1, target);

}

return binarySearchRecur(A, mid+1, high, target);

}

// 단방향(메타) 이진 검색 버전 : A[0 ~ N-1]

int metaBinarySearch(int A[], int low, int high, int target){

int bin = 1, idx = 0;

while(bin <= high) bin <<= 1;

for(bin >>= 1;; bin >>= 1){

int i = idx + bin;

if( i <= high && A[i] <= target){

if(A[i] == target) return i;

idx = i;

}

if(bin == 0) break;

}

return -1;

}

```

```python

def binarySearch(array, value, low, high):

if low > high:

return False

mid = (low+high) // 2

if array[mid] > value:

return binarySearch(array, value, low, mid-1)

elif array[mid] < value:

return binarySearch(array, value, mid+1, high)

else:

return mid

```

```java

public int binarySearch(int[] arr, int target) {

int start = 0;

int end = arr.length - 1;

int mid = 0;

while (start <= end) {

mid = (start + end) / 2;

if (target == arr[mid]) {

return mid;

} else if (arr[mid] < target) {

start = mid + 1;

} else if (target < arr[mid]) {

end = mid - 1;

}

}

throw new NoSuchElementException("can't find target.");

}

7. 1. C

cpp

// 반복문 버전 : A[0 ~ N-1]

int binarySearch(int A[], int low, int high, int target){

while(low <= high){

int mid = (low + high) / 2;

if(A[mid] == target) return mid;

if(A[mid] > target) high = mid - 1;

else low = mid + 1;

}

return -1;

}

// 재귀 버전 : A[0 ~ N-1]

int binarySearchRecur(int A[], int low, int high, int target){

if(low > high) return -1;

int mid = (low + high) / 2;

if(A[mid] == target) return mid;

if(A[mid] > target){

return binarySearchRecur(A, low, mid-1, target);

}

return binarySearchRecur(A, mid+1, high, target);

}

// 단방향(메타) 이진 검색 버전 : A[0 ~ N-1]

int metaBinarySearch(int A[], int low, int high, int target){

int bin = 1, idx = 0;

while(bin <= high) bin <<= 1;

for(bin >>= 1;; bin >>= 1){

int i = idx + bin;

if( i <= high && A[i] <= target){

if(A[i] == target) return i;

idx = i;

}

if(bin == 0) break;

}

return -1;

}

```

```c

int binary_search(int ary[], int key, int imin, int imax) {

if (imax < imin) {

return KEY_NOT_FOUND;

} else {

int imid = imin + (imax - imin) / 2;

if (ary[imid] > key) {

return binary_search(ary, key, imin, imid - 1);

} else if (ary[imid] < key) {

return binary_search(ary, key, imid + 1, imax);

} else {

return imid;

}

}

}

7. 2. Python

python

def binarySearch(array, value, low, high):

if low > high:

return False

mid = (low + high) // 2

if array[mid] > value:

return binarySearch(array, value, low, mid - 1)

elif array[mid] < value:

return binarySearch(array, value, mid + 1, high)

else:

return mid

7. 3. Java

java

public int binarySearch(int[] arr, int target) {

int start = 0;

int end = arr.length - 1;

int mid = 0;

while (start <= end) {

mid = (start + end) / 2;

if (target == arr[mid]) {

return mid;

} else if (arr[mid] < target) {

start = mid + 1;

} else if (target < arr[mid]) {

end = mid - 1;

}

}

throw new NoSuchElementException("can't find target.");

}

8. 라이브러리 지원

C는 표준 라이브러리에서 `bsearch()` 함수를 제공하며, 이는 일반적으로 이진 검색으로 구현되지만 공식 표준에서는 이를 요구하지 않는다.^[33] C++의 표준 라이브러리는 `binary_search()`, `lower_bound()`, `upper_bound()` 및 `equal_range()` 함수를 제공한다. D의 표준 라이브러리인 Phobos는 `std.range` 모듈에서 `SortedRange` 형식을 제공하며, 이 형식은 기본적으로 임의 접근을 제공하는 범위에 대해 이진 검색 기술을 사용하는 `contains()`, `equaleRange()`, `lowerBound()` 및 `trisect()` 메서드를 포함한다.^[34] COBOL은 COBOL 정렬 테이블에서 이진 검색을 수행하기 위해 `SEARCH ALL` 동사를 제공한다.^[35] Go의 `sort` 표준 라이브러리 패키지는 일반 이진 검색을 구현하는 `Search`, `SearchInts`, `SearchFloat64s` 및 `SearchStrings` 함수와, 각각 정수, 부동 소수점 숫자 및 문자열 슬라이스 검색을 위한 특정 구현을 포함한다.^[36]

Java는 표준 `java.util` 패키지의 `Arrays` 및 `Collections` 클래스에서 Java 배열 및 `List`에 대해 이진 검색을 수행하기 위한 일련의 오버로드된 `binarySearch()` 정적 메서드를 제공한다.^[37]^[38] .NET Framework 2.0은 컬렉션 기본 클래스에서 이진 검색 알고리즘의 정적 제네릭 버전을 제공한다. 예를 들어 `System.Array`의 `BinarySearch(T[] array, T value)` 메서드가 있다.^[39] Objective-C의 경우, Cocoa 프레임워크는 Mac OS X 10.6 이상에서 `NSArray -indexOfObject:inSortedRange:options:usingComparator:` 메서드를 제공한다.^[40] 애플의 Core Foundation C 프레임워크는 `CFArrayBSearchValues()` 함수도 포함한다.^[41] Python은 각 삽입 후 목록을 정렬하지 않고도 정렬된 순서로 목록을 유지하는 `bisect` 모듈을 제공한다.^[42] Ruby의 Array 클래스는 내장된 근사 일치를 포함하는 `bsearch` 메서드를 포함한다. Rust의 슬라이스 원시 형식은 `binary_search()`, `binary_search_by()`, `binary_search_by_key()` 및 `partition_point()`를 제공한다.^[43]

참조

_[1] 학회 A modification to the half-interval search (binary search) method https://dl.acm.org/c[...] ACM 1976-04-22
_[2] MathWorld Binary search
_[3] 학술지 Average binary search length for dense ordered lists 1971-09-01
_[4] 학술지 Structure and use of ALGOL 60 1962-04-01
_[5] 학술지 Analytic derivation of comparisons in binary search 1997
_[6] 학술지 Array Layouts for Comparison-Based Searching
_[7] 학술지 Optimal bounds for the predecessor problem and related problems 2001
_[8] 학술지 Dynamic perfect hashing: upper and lower bounds 1994-08
_[9] 웹사이트 Hash tables http://cglab.ca/~mor[...] 2016-03-28
_[10] Citation Judy IV shop manual http://judy.sourcefo[...] Hewlett-Packard
_[11] 학회 Cuckoo filter: practically better than Bloom 2014
_[12] 학술지 Space/time trade-offs in hash coding with allowable errors 1970
_[13] 학술지 Interpolation search—a log log ''n'' search 1978
_[14] 학회 Lower bounds for intersection searching and fractional cascading in higher dimension https://dl.acm.org/c[...] ACM 2001-07-06
_[15] 학술지 Lower bounds for intersection searching and fractional cascading in higher dimension http://www.cs.prince[...] 2004-03-01
_[16] 학회 Deterministic and probabilistic binary search in graphs 2016
_[17] 학회 The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) http://www2.lns.mit.[...] 2008
_[18] 학술지 Searching with known error probability 1989
_[19] 학회 Coping with errors in binary search procedures
_[20] 학술지 Searching games with errors—fifty years of coping with liars 2002
_[21] 학술지 On a problem in information theory
_[22] 학술지 Quantum complexities of ordered searching, sorting, and element distinctness 2002
_[23] 학술지 Quantum algorithms for the ordered search problem via semidefinite programming 2007
_[24] 학회 A fast quantum mechanical algorithm for database search 1996
_[25] 학술지 Addressing for random-access storage 1957
_[26] 웹인용 2^''n''−1 http://oeis.org/A000[...] 2016-06-08
_[27] 서적 Combinatorial Analysis
_[28] 학술지 Fractional cascading: I. A data structuring technique http://www.cs.prince[...]
_[29] Citation Fractional cascading: II. Applications http://www.cs.prince[...]
_[30] 학술지 Textbook errors in binary searching
_[31] 웹사이트 Extra, extra – read all about it: nearly all binary searches and mergesorts are broken http://googleresearc[...] 2006-06-02
_[32] 학술지 On computing the semi-sum of two integers http://www.di.unipi.[...] 2003
_[33] 웹사이트 bsearch – binary search a sorted table http://pubs.opengrou[...] The Open Group 2013
_[34] 웹사이트 std.range - D Programming Language https://dlang.org/ph[...] 2020-04-29
_[35] Citation COBOL ANSI-85 programming reference manual 2012
_[36] 웹사이트 Package sort http://golang.org/pk[...] 2016-04-28
_[37] 웹사이트 java.util.Arrays https://docs.oracle.[...] Oracle Corporation 2016-05-01
_[38] 웹사이트 java.util.Collections https://docs.oracle.[...] Oracle Corporation 2016-05-01
_[39] 웹사이트 List.BinarySearch method (T) https://msdn.microso[...] 2016-04-10
_[40] 웹사이트 NSArray https://developer.ap[...] Apple Inc. 2016-05-01
_[41] 웹사이트 CFArray https://developer.ap[...] Apple Inc. 2016-05-01
_[42] 웹사이트 8.6. bisect — Array bisection algorithm https://docs.python.[...] Python Software Foundation 2018-03-26
_[43] 웹사이트 Primitive Type slice https://doc.rust-lan[...] The Rust Foundation 2024-05-25
_[44] 문서 O記法では定数倍を無視できるので、単に $O(\log n)$ とも書ける。
_[45] 서적 Sorting and Searching Addison-Wesley
_[46] 논문 Textbook errors in binary searching
_[47] 웹사이트 Bug ID: JDK-5045582 (coll) binarySearch() fails for size larger than 1<<30 http://bugs.java.com[...]

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com