이진 검색

컴퓨터 과학에서 **이진 검색**(binary search) 또는 **반간격 검색**(half-interval search), **로그 검색**(logarithmic search) 또는 **이진 찹(binary chop)**은 정렬된 배열 내에서 목표 값의 위치를 찾는 검색 알고리즘이다. 이진 검색은 목표 값을 배열의 중간 요소와 비교한다. 같지 않으면 목표가 존재할 수 없는 절반을 제거하고, 나머지 절반에서 다시 중간 요소를 목표 값과 비교하여 검색을 계속하며, 목표 값을 찾을 때까지 반복한다. 남은 절반이 비어 있는 상태로 검색이 끝나면 목표는 배열에 없는 것이다.

이진 검색은 로그 시간으로 실행되며 최악의 경우 O(\log n)번의 비교를 수행한다. 여기서 n은 배열의 요소 수이다. 이진 검색은 작은 배열을 제외하고는 순차 검색보다 빠르다. 그러나 이진 검색을 적용하려면 배열이 먼저 정렬되어 있어야 한다. 해시 테이블과 같이 빠른 검색을 위해 설계된 특수 자료 구조가 있으며, 이들은 이진 검색보다 효율적으로 검색할 수 있다. 그러나 이진 검색은 배열에 없는 경우에도 목표 값에 상대적인 다음으로 작은 또는 다음으로 큰 요소를 찾는 것과 같은 더 넓은 범위의 문제를 해결하는 데 사용될 수 있다.

이진 검색에는 수많은 변형이 있다. 특히, 분할 캐스케이딩은 여러 배열에서 동일한 값에 대한 이진 검색 속도를 높인다. 분할 캐스케이딩은 계산기하학 및 기타 여러 분야에서 많은 검색 문제를 효율적으로 해결한다. 지수 검색은 이진 검색을 무한정 목록으로 확장한다. 이진 탐색 트리 및 B 트리 자료 구조는 이진 검색을 기반으로 한다.

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

### 절차
A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}와 같이 정렬된 n개의 요소 또는 레코드 A 배열과 목표 값 T가 주어졌을 때, 다음 서브루틴은 이진 검색을 사용하여 A 내에서 T의 인덱스를 찾는다.
# L을 0으로, R을 n-1로 설정한다.
# 만약 L>R이면, 검색은 실패로 종료된다.
# m (중앙 요소의 위치)을 L에 \frac{R-L}{2}의 바닥을 더한 값으로 설정한다. 이는 \frac{R-L}{2}보다 작거나 같은 가장 큰 정수이다.
# 만약 A_m 이면, L을 m+1로 설정하고 2단계로 이동한다.
# 만약 A_m > T이면, R을 m-1로 설정하고 2단계로 이동한다.
# 이제 A_m = T이므로, 검색이 완료되었다. m을 반환한다.

이 반복적인 절차는 두 변수 L과 R로 검색 경계를 추적한다. 이 절차는 다음과 같이 의사코드로 표현될 수 있으며, 변수 이름과 형식은 위와 동일하고, `floor`는 바닥 함수이며, `unsuccessful`은 검색 실패를 나타내는 특정 값을 의미한다.
섬네일|right|binary-search
 **function** binary_search(A, n, T) **is**
     L := 0
     R := n &minus; 1
     **while** L ≤ R **do**
         m := L + floor((R - L) / 2)
         **if** A[m]  T **then**
             R := m &minus; 1
         **else**:
             **return** m
     **return** unsuccessful

대안적으로, 알고리즘은 \frac{R-L}{2}의 천장 함수를 취할 수도 있다. 이는 목표 값이 배열에 여러 번 나타나는 경우 결과가 달라질 수 있다.

#### 대체 절차
위 절차에서 알고리즘은 각 반복마다 중간 요소(m)가 목표(T)와 같은지 확인한다. 일부 구현에서는 각 반복에서 이 확인을 생략한다. 알고리즘은 하나의 요소만 남았을 때(L=R일 때)만 이 확인을 수행한다. 이는 각 반복에서 하나의 비교가 제거되므로 더 빠른 비교 루프를 초래하며, 평균적으로 한 번의 반복만 더 필요로 한다.

헤르만 보텐브루흐(Hermann Bottenbruch)는 1962년에 이 검사를 생략한 첫 번째 구현을 발표했다.

# L을 0으로, R을 n-1로 설정한다.
# L \neq R인 동안,
## m (중앙 요소의 위치)을 L에 \frac{R-L}{2}의 천장을 더한 값으로 설정한다. 이는 \frac{R-L}{2}보다 크거나 같은 가장 작은 정수이다.
## 만약 A_m > T이면, R을 m-1로 설정한다.
## 그렇지 않으면, A_m \leq T이며, L을 m으로 설정한다.
# 이제 L=R이므로 검색이 완료된다. 만약 A_L=T이면, L을 반환한다. 그렇지 않으면 검색은 실패로 종료된다.

여기서 `ceil`은 천장 함수이고, 이 버전의 의사코드는 다음과 같다.

 **function** binary_search_alternative(A, n, T) **is**
     L := 0
     R := n &minus; 1
     **while** L != R **do**
         m := L + ceil((R - L) / 2)
         **if** A[m] > T **then**
             R := m &minus; 1
         **else**:
             L := m
     **if** A[L] = T **then**
         **return** L
     **return** unsuccessful

### 중복 요소
이 절차는 배열에 중복 요소가 있더라도 해당 요소가 목표 값과 같은 임의의 인덱스를 반환할 수 있다. 예를 들어, 검색할 배열이 [1,2,3,4,4,5,6,7]이고 목표가 4인 경우, 알고리즘이 4번째(인덱스 3) 또는 5번째(인덱스 4) 요소를 반환하는 것은 올바르다. 일반적인 절차는 이 경우 4번째 요소(인덱스 3)를 반환한다. 항상 첫 번째 중복을 반환하는 것은 아니다(예를 들어 [1,2,4,4,4,5,6,7]의 경우 여전히 4번째 요소를 반환한다). 그러나 배열에 중복된 목표 값이 있는 경우 가장 왼쪽 요소 또는 가장 오른쪽 요소를 찾아야 할 때가 있다. 위 예에서 4번째 요소는 값 4의 가장 왼쪽 요소이고, 5번째 요소는 값 4의 가장 오른쪽 요소이다. 위의 대체 절차는 그러한 요소가 존재하면 항상 가장 오른쪽 요소의 인덱스를 반환한다.

#### 가장 왼쪽 요소를 찾는 절차
가장 왼쪽 요소를 찾으려면 다음 절차를 사용할 수 있다.

# L을 0으로, R을 n으로 설정한다.
# L 인 동안,
## m (중앙 요소의 위치)을 L에 \frac{R-L}{2}의 바닥을 더한 값으로 설정한다. 이는 \frac{R-L}{2}보다 작거나 같은 가장 큰 정수이다.
## 만약 A_m 이면, L을 m+1로 설정한다.
## 그렇지 않으면, A_m \geq T이며, R을 m으로 설정한다.
# L을 반환한다.

만약 L 이고 A_L = T이면, A_L은 T와 같은 가장 왼쪽 요소이다. T가 배열에 없더라도 L은 배열 내 T의 순위이거나, T보다 작은 배열 요소의 개수이다.

여기서 `floor`는 바닥 함수이며, 이 버전의 의사코드는 다음과 같다.

 **function** binary_search_leftmost(A, n, T):
     L := 0
     R := n
     **while** L L을 0으로, R을 n으로 설정한다.
# L 인 동안,
## m (중앙 요소의 위치)을 L에 \frac{R-L}{2}의 바닥을 더한 값으로 설정한다. 이는 \frac{R-L}{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보다 큰 요소의 개수이다.

여기서 `floor`는 바닥 함수이며, 이 버전의 의사코드는 다음과 같다.

 **function** binary_search_rightmost(A, n, T):
     L := 0
     R := n
     **while** L  T:
             R := m
         **else**:
             L := m + 1
     **return** R - 1

### 근사 일치
섬네일|upright=1.5|이진 검색은 근사 일치를 계산하도록 조정될 수 있다. 위 예시에서는 배열에 없는 목표 값 <math>5</math>에 대한 순위, 선행자, 후속자, 그리고 최근접 이웃이 표시되어 있다.
위 절차는 목표 값의 위치를 찾는 정확한 일치만을 수행한다. 그러나 이진 검색은 정렬된 배열에서 작동하므로 근사 일치를 수행하도록 이진 검색을 확장하는 것은 간단하다. 예를 들어, 이진 검색은 주어진 값에 대해 그 순위(더 작은 요소의 수), 선행자(다음으로 작은 요소), 후속자(다음으로 큰 요소), 그리고 최근접 이웃을 계산하는 데 사용될 수 있다. 두 값 사이의 요소 수를 찾는 범위 질의는 두 개의 순위 질의로 수행될 수 있다.
* 순위 질의는 가장 왼쪽 요소를 찾는 절차로 수행할 수 있다. 목표 값보다 작은 요소의 개수가 절차에 의해 반환된다.
* 선행자 질의는 순위 질의로 수행할 수 있다. 목표 값의 순위가 r이면, 그 선행자는 r-1이다.
* 후속자 질의의 경우, 가장 오른쪽 요소를 찾는 절차를 사용할 수 있다. 목표 값에 대해 절차를 실행한 결과가 r이면, 목표 값의 후속자는 r+1이다.
* 목표 값의 최근접 이웃은 선행자 또는 후속자 중 더 가까운 쪽이다.
* 범위 질의도 간단하다. 두 값의 순위를 알면, 첫 번째 값보다 크거나 같고 두 번째 값보다 작은 요소의 수는 두 순위의 차이이다. 이 개수는 범위의 끝점이 범위의 일부로 간주되어야 하는지 여부와 배열에 해당 끝점과 일치하는 항목이 포함되어 있는지 여부에 따라 1만큼 위아래로 조정될 수 있다.

## 성능
[섬네일|upright|이진 검색을 나타내는 [트리 (자료 구조)|트리. 여기서 검색되는 배열은 [20, 30, 40, 50, 80, 90, 100]이고, 목표 값은 40이다.]]
섬네일|upright=1.6|최악의 경우는 검색이 트리의 가장 깊은 수준에 도달할 때이며, 최선의 경우는 목표 값이 중간 요소일 때이다.

비교 횟수 측면에서 이진 검색의 성능은 이진 트리의 절차 실행을 통해 분석할 수 있다. 트리의 루트 노드는 배열의 중간 요소이다. 하위 절반의 중간 요소는 루트의 왼쪽 자식 노드이고, 상위 절반의 중간 요소는 루트의 오른쪽 자식 노드이다. 나머지 트리는 유사한 방식으로 구성된다. 루트 노드부터 시작하여, 목표 값이 고려 중인 노드보다 작거나 큰지에 따라 왼쪽 또는 오른쪽 서브트리를 탐색한다.

최악의 경우, 이진 검색은 \lfloor \log_2 (n) + 1 \rfloor번의 비교 루프를 수행한다. 여기서 \lfloor\cdot \rfloor 표기법은 인자보다 작거나 같은 가장 큰 정수를 반환하는 바닥 함수를 나타내고, \log_2는 이진 로그이다. 이는 최악의 경우가 검색이 트리의 가장 깊은 수준에 도달할 때 발생하며, 어떤 이진 검색 트리든 항상 \lfloor \log_2 (n) + 1 \rfloor 수준을 가지기 때문이다.

최악의 경우는 목표 요소가 배열에 없을 때도 발생할 수 있다. 만약 n이 2의 거듭제곱보다 1 작은 수라면, 항상 그렇다. 그렇지 않으면, 검색이 트리의 가장 깊은 수준에 도달하면 \lfloor \log_2 (n) + 1 \rfloor번의 반복을 수행할 수 있다. 그러나 검색이 트리의 두 번째로 깊은 수준에서 끝나는 경우, 최악의 경우보다 한 번 적은 \lfloor \log_2 (n) \rfloor번의 반복을 수행할 수도 있다.

평균적으로 각 요소를 검색할 확률이 같다고 가정할 때, 목표 요소가 배열에 있으면 이진 검색은 \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n번의 반복을 수행한다. 이는 약 \log_2(n) - 1번의 반복과 같다. 목표 요소가 배열에 없는 경우, 요소 사이와 외부 범위가 검색될 확률이 같다고 가정할 때, 이진 검색은 평균적으로 \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)번의 반복을 수행한다.

최선의 경우, 목표 값이 배열의 중간 요소일 때, 한 번의 반복 후에 해당 위치가 반환된다.

반복 횟수 측면에서 요소 비교만으로 작동하는 어떤 검색 알고리즘도 이진 검색보다 나은 평균 및 최악의 성능을 보일 수 없다. 이진 검색을 나타내는 비교 트리는 트리의 가장 낮은 수준 위에 있는 모든 수준이 완전히 채워져 있으므로 가능한 가장 적은 수준을 갖는다. 그렇지 않으면 검색 알고리즘은 한 번의 반복에서 적은 수의 요소만 제거하여 평균 및 최악의 경우 필요한 반복 횟수를 늘린다. 이는 다른 비교 기반 검색 알고리즘의 경우에도 마찬가지인데, 일부 목표 값에 대해 더 빠르게 작동할 수 있지만, 모든 요소에 대한 평균 성능은 이진 검색보다 나쁘다. 배열을 절반으로 나누어 이진 검색은 두 서브배열의 크기가 가능한 한 유사하도록 보장한다.

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

### 평균적인 경우의 유도
이진 검색이 수행하는 평균 반복 횟수는 각 요소를 검색할 확률에 따라 달라진다. 성공적인 검색과 실패한 검색의 평균적인 경우는 다르다. 성공적인 검색의 경우 각 요소가 검색될 확률이 같다고 가정한다. 실패한 검색의 경우 요소 사이와 외부 구간이 검색될 확률이 같다고 가정한다. 성공적인 검색의 평균적인 경우는 모든 요소를 정확히 한 번씩 검색하는 데 필요한 반복 횟수를 요소의 수 n으로 나눈 값이다. 실패한 검색의 평균적인 경우는 모든 구간에서 요소를 정확히 한 번씩 검색하는 데 필요한 반복 횟수를 n + 1개의 구간으로 나눈 값이다.

#### 성공적인 검색

이진 트리 표현에서 성공적인 검색은 루트에서 목표 노드까지의 경로, 즉 내부 경로로 나타낼 수 있다. 경로의 길이는 경로가 통과하는 가장자리(노드 간 연결)의 수이다. 해당 경로 길이가 일 때, 검색이 수행하는 반복 횟수는 초기 반복을 포함하여 l + 1이다. 내부 경로 길이는 모든 고유한 내부 경로 길이의 합이다. 루트에서 어떤 단일 노드까지 하나의 경로만 존재하므로, 각 내부 경로는 특정 요소에 대한 검색을 나타낸다. 개의 요소가 양의 정수이고 내부 경로 길이가 I(n)이면, 성공적인 검색의 평균 반복 횟수 T(n) = 1 + \frac{I(n)}{n}이며, 초기 반복을 세기 위해 1이 더해진다.

이진 검색은 비교를 통한 검색에 최적의 알고리즘이므로, 이 문제는 개의 노드를 가진 모든 이진 트리의 최소 내부 경로 길이를 계산하는 것으로 귀결되며, 이는 다음과 같다.


I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor


예를 들어, 7개 요소 배열에서 루트는 한 번의 반복이 필요하고, 루트 아래의 두 요소는 두 번의 반복, 그 아래의 네 요소는 세 번의 반복이 필요하다. 이 경우 내부 경로 길이는 다음과 같다.


\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10


평균 반복 횟수는 평균적인 경우에 대한 방정식에 따라 1 + \frac{10}{7} = 2 \frac{3}{7}이 될 것이다. I(n)에 대한 합은 다음과 같이 단순화될 수 있다.


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


I(n)에 대한 방정식을 T(n)에 대한 방정식에 대입하면 다음과 같다.


T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n


정수 의 경우, 이는 위에서 명시된 성공적인 검색의 평균적인 경우에 대한 방정식과 동일하다.

#### 실패한 검색
실패한 검색은 외부 노드를 추가하여 트리를 확장함으로써 나타낼 수 있으며, 이는 확장 이진 트리를 형성한다. 내부 노드, 즉 트리에 존재하는 노드가 두 개 미만의 자식 노드를 가지면, 각 내부 노드가 두 자식을 갖도록 외부 노드라는 추가 자식 노드가 추가된다. 이렇게 함으로써, 실패한 검색은 외부 노드로의 경로로 나타낼 수 있으며, 그 부모는 마지막 반복 동안 남아 있는 단일 요소이다. 외부 경로는 루트에서 외부 노드까지의 경로이다. 외부 경로 길이는 모든 고유한 외부 경로 길이의 합이다. 양의 정수인 n개의 요소가 있고 외부 경로 길이가 E(n)이면, 실패한 검색의 평균 반복 횟수 T'(n)=\frac{E(n)}{n+1}이며, 초기 반복을 계산하기 위해 1이 더해진다. 외부 경로 길이는 n이 아닌 n+1로 나뉜다. 이는 배열의 요소 사이와 외부를 나타내는 n+1개의 외부 경로가 있기 때문이다.

이 문제는 유사하게 n개의 노드를 가진 모든 이진 트리의 최소 외부 경로 길이를 결정하는 것으로 축소될 수 있다. 모든 이진 트리에 대해 외부 경로 길이는 내부 경로 길이에 2n을 더한 값과 같다. I(n)에 대한 방정식을 대입하면 다음과 같다.


E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}


E(n)에 대한 방정식을 T'(n)에 대한 방정식에 대입하면, 실패한 검색의 평균적인 경우를 결정할 수 있다.


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


#### 대체 절차의 성능
위에 정의된 이진 검색 절차의 각 반복은 중간 요소가 각 반복에서 목표와 같은지 확인하는 한두 번의 비교를 수행한다. 각 요소가 검색될 가능성이 같다고 가정하면, 각 반복은 평균적으로 1.5번의 비교를 수행한다. 알고리즘의 한 변형은 검색 끝에서 중간 요소가 목표와 같은지 확인한다. 평균적으로 이는 각 반복에서 절반의 비교를 제거한다. 이는 대부분의 컴퓨터에서 반복당 소요되는 시간을 약간 단축시킨다. 그러나 검색이 평균적으로 한 번 더 반복되어 최대 반복 횟수를 보장한다. 최악의 경우 비교 루프가 \lfloor \log_2 (n) + 1 \rfloor번만 수행되기 때문에, 반복당 효율성의 약간의 증가는 매우 큰 n을 제외하고는 추가 반복을 상쇄하지 못한다.

### 추가 고려 사항

#### 비교 비용
이진 검색의 성능을 분석할 때 또 다른 고려 사항은 두 요소를 비교하는 데 필요한 시간이다. 정수와 문자열의 경우, 인코딩 길이(일반적으로 비트 수)가 증가함에 따라 필요한 시간이 선형적으로 증가한다. 예를 들어, 64비트 부호 없는 정수 쌍을 비교하는 데는 32비트 부호 없는 정수 쌍을 비교하는 것보다 최대 두 배의 비트를 비교해야 한다. 최악의 경우는 정수가 같을 때 발생한다. 이는 요소의 인코딩 길이가 큰 경우(예: 큰 정수형 또는 긴 문자열) 비교 비용이 많이 들 때 중요할 수 있다. 또한, 부동소수점 값(실수의 가장 일반적인 디지털 표현)을 비교하는 것은 정수나 짧은 문자열을 비교하는 것보다 비용이 더 많이 드는 경우가 많다.

빠른 부동소수점 비교는 정수로 비교하는 것을 통해 가능하다. 그러나 이러한 종류의 비교는 전순서를 형성하며, 모든 부동소수점 값이 서로 다르게 비교되고 자신과 동일하게 비교된다. 이는 -0.0이 0.0과 같아야 하고 NaN이 다른 어떤 값과도 자신과도 같게 비교되지 않아야 하는 일반적인 비교와는 다르다.

#### 분기 예측
스틸 뱅크 커먼 리스프 기여자 폴 쿠옹(Paul Khuong)에 따르면, 이진 검색은 데이터 의존적인 특성에도 불구하고 분기 예측 오류가 거의 발생하지 않는다. 이는 대부분의 이진 검색이 분기 대신 조건부 이동으로 표현될 수 있기 때문이다. 대부분의 로그 분할 정복 검색 알고리즘에도 동일하게 적용된다.

#### 캐시 사용량

대부분의 컴퓨터 아키텍처에서 프로세서는 RAM과 별도로 하드웨어 캐시를 가지고 있다. 캐시는 프로세서 자체 내에 위치하기 때문에 접근 속도가 훨씬 빠르지만, 일반적으로 RAM보다 훨씬 적은 데이터를 저장한다. 따라서 대부분의 프로세서는 최근에 접근한 메모리 위치와 그 주변 메모리 위치를 저장한다. 예를 들어, 배열 요소에 접근할 때, 요소 자체는 RAM에 인접하게 저장된 요소들과 함께 저장되어, 서로 인덱스가 가까운 배열 요소들을 순차적으로 접근하는 것이 더 빠르다(참조 국부성). 정렬된 배열에서 이진 검색은 배열이 크면 먼 메모리 위치로 점프할 수 있으며, 이는 순차적으로 요소에 접근하는 알고리즘(예: 순차 검색 및 해시 테이블의 선형 탐사)과는 다르다. 이는 대부분의 시스템에서 대규모 배열에 대한 이진 검색의 실행 시간을 약간 증가시킨다.

폴 쿠옹(Paul Khuong)은 512KiB 이상의 2의 거듭제곱 크기를 가진 대규모 배열에 대한 이진 검색이 CPU 캐시 구현 방식과 관련하여 추가적인 문제를 일으키는 경향이 있다고 지적했다. 특히, 변환 색인 버퍼(TLB)는 종종 내용 주소화 기억장치(CAM)로 구현되며, "키"는 일반적으로 요청된 주소의 하위 비트이다. 정확히 2의 거듭제곱 크기를 가진 배열에서 검색할 때, 동일한 하위 비트를 가진 메모리 주소가 접근되는 경향이 있어 CAM을 가져오는 데 사용되는 "키"와 충돌("앨리어싱")이 발생한다. 일반적인 TLB는 4방향 연관(4-way associative) 방식이므로, 동일한 "키"에 최대 4개의 주소만 처리할 수 있으며, 그 이후에는 TLB 스레싱이 발생한다. (다른 CPU 캐시 수준도 유사한 설정을 사용하지만, 더 적은 영역을 더 높은 방식(일반적으로 8 또는 16)으로 관리하므로 덜 영향을 받는다.) 이는 이진 검색의 분할 지점을 정확히 중간 대신 로 오프셋하여 방지할 수 있다.

## 이진 검색 대 다른 방식
이진 검색을 사용하는 정렬된 배열은 삽입 및 삭제 작업이 검색과 함께 번갈아 수행될 때 매우 비효율적인 해결책으로, 각 작업에 O(n) 시간이 걸린다. 또한 정렬된 배열은 특히 요소가 배열에 자주 삽입될 때 메모리 사용을 복잡하게 만들 수 있다. 훨씬 더 효율적인 삽입 및 삭제를 지원하는 다른 자료 구조가 있다. 이진 검색은 정확한 일치 및 집합 멤버십(목표 값이 값 컬렉션에 있는지 여부 확인)을 수행하는 데 사용될 수 있다. 더 빠른 정확한 일치 및 집합 멤버십을 지원하는 자료 구조가 있다. 그러나 다른 많은 검색 방식과 달리 이진 검색은 효율적인 근사 일치에 사용될 수 있으며, 일반적으로 값의 유형이나 구조에 관계없이 O(\log n) 시간으로 이러한 일치를 수행한다. 또한 가장 작은 요소와 가장 큰 요소를 찾는 것과 같은 일부 작업은 정렬된 배열에서 효율적으로 수행할 수 있다.

### 순차 검색
순차 검색은 목표 값을 찾을 때까지 모든 레코드를 확인하는 간단한 검색 알고리즘이다. 순차 검색은 연결 리스트에서 수행될 수 있으며, 이는 배열보다 빠른 삽입 및 삭제를 허용한다. 이진 검색은 배열이 짧은 경우를 제외하고는 정렬된 배열에 대해 순차 검색보다 빠르지만, 배열은 사전에 정렬되어 있어야 한다. 퀵 정렬과 합병 정렬과 같이 요소 비교에 기반한 모든 정렬 알고리즘은 최악의 경우 최소한 O(n \log n)번의 비교를 필요로 한다. 순차 검색과 달리 이진 검색은 효율적인 근사 일치에 사용될 수 있다. 가장 작은 요소와 가장 큰 요소를 찾는 것과 같은 일부 작업은 정렬된 배열에서는 효율적으로 수행할 수 있지만 정렬되지 않은 배열에서는 불가능하다.

### 트리
[섬네일|right|[이진 탐색 트리는 이진 검색과 유사한 알고리즘을 사용하여 검색된다.]]

이진 탐색 트리는 이진 검색의 원리에 따라 작동하는 이진 트리 자료 구조이다. 트리의 레코드는 정렬된 순서로 배열되며, 트리 내의 각 레코드는 이진 검색과 유사한 알고리즘을 사용하여 검색할 수 있으며, 평균적으로 로그 시간이 소요된다. 이진 탐색 트리에서의 삽입 및 삭제 또한 평균적으로 로그 시간이 필요하다. 이는 정렬된 배열의 선형 시간 삽입 및 삭제보다 빠를 수 있으며, 이진 트리는 범위 및 근사 질의를 포함하여 정렬된 배열에서 가능한 모든 작업을 수행하는 능력을 유지한다.

그러나 이진 검색 트리는 불완전하게 균형을 이룰 가능성이 높으므로 이진 검색보다 성능이 약간 떨어지기 때문에 이진 검색이 검색에 더 효율적인 경우가 많다. 이는 자가 균형 이진 탐색 트리에도 적용되는데, 이는 자체 노드의 균형을 맞추는 이진 검색 트리이지만 가능한 가장 적은 수의 수준을 가진 트리를 거의 생성하지 않기 때문이다. 균형 이진 검색 트리를 제외하고는 트리가 두 자식을 가진 내부 노드가 거의 없어 심하게 불균형할 수 있으며, 이로 인해 평균 및 최악의 검색 시간이 n번의 비교에 가까워질 수 있다. 이진 검색 트리는 정렬된 배열보다 더 많은 공간을 차지한다.

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

### 해싱
연관 배열을 구현하는 데 있어 해시 함수를 사용하여 키를 레코드에 매핑하는 자료 구조인 해시 테이블은 일반적으로 레코드 정렬 배열에 대한 이진 검색보다 빠르다. 대부분의 해시 테이블 구현은 평균적으로 분할 상환 상수 시간만 필요로 한다. 그러나 해싱은 실패한 검색에서 주어진 유일한 정보가 목표가 어떤 레코드에도 존재하지 않는다는 것이기 때문에, 다음으로 작은 키, 다음으로 큰 키, 가장 가까운 키를 계산하는 것과 같은 근사 일치에는 유용하지 않다. 이진 검색은 이러한 일치에 이상적이며, 로그 시간으로 수행한다. 이진 검색은 또한 근사 일치를 지원한다. 가장 작은 요소와 가장 큰 요소를 찾는 것과 같은 일부 작업은 정렬된 배열에서는 효율적으로 수행할 수 있지만 해시 테이블에서는 불가능하다.

### 집합 멤버십 알고리즘
검색과 관련된 문제는 집합 멤버십이다. 이진 검색과 같이 조회를 수행하는 모든 알고리즘은 집합 멤버십에도 사용될 수 있다. 집합 멤버십에 더 specifically 적합한 다른 알고리즘이 있다. 비트 배열은 가장 간단하며, 키의 범위가 제한될 때 유용하다. 이는 키 범위 내의 각 키를 나타내는 비트 컬렉션을 압축하여 저장한다. 비트 배열은 매우 빠르며, O(1) 시간만 필요로 한다. Judy 배열의 Judy1 유형은 64비트 키를 효율적으로 처리한다.

근사 결과의 경우, 해싱 기반의 다른 확률적 자료 구조인 블룸 필터는 비트 배열과 여러 해시 함수를 사용하여 키를 인코딩함으로써 집합의 키를 저장한다. 블룸 필터는 대부분의 경우 비트 배열보다 훨씬 공간 효율적이며 속도도 크게 느리지 않다. k개의 해시 함수를 사용하면 멤버십 질의에 O(k) 시간만 필요하다. 그러나 블룸 필터는 거짓 양성 문제를 겪는다.

### 다른 자료 구조
이진 검색과 정렬된 배열에서 사용할 수 있는 다른 연산 모두에 대해 일부 경우 이진 검색을 개선할 수 있는 자료 구조가 존재한다. 예를 들어, 검색, 근사 일치 및 정렬된 배열에서 사용할 수 있는 연산은 판 엠데 보아스 트리, 퓨전 트리, 트라이, 비트 배열과 같은 특수 자료 구조에서 이진 검색보다 효율적으로 수행될 수 있다. 이러한 특수 자료 구조는 특정 속성(일반적으로 작은 정수인 키)을 가진 키의 속성을 활용하기 때문에 보통 더 빠르며, 따라서 그 속성이 없는 키에 대해서는 시간 또는 공간 소모적일 것이다. 키가 정렬될 수 있는 한, 이러한 연산은 키에 관계없이 정렬된 배열에서 항상 효율적으로 수행될 수 있다. Judy 배열과 같은 일부 구조는 효율성과 근사 일치 수행 능력을 유지하면서 이를 완화하기 위해 여러 접근 방식을 조합하여 사용한다.

## 변형

### 균등 이진 검색

[섬네일|upright=1.0|[균등 이진 검색은 특정 경계 대신 현재 반복에서 다음 두 개의 가능한 중간 요소와의 인덱스 차이를 저장한다.]]
균등 이진 검색은 하한 및 상한 대신 현재 반복에서 다음 반복으로 중간 요소의 인덱스 차이를 저장한다. 차이가 포함된 순람표는 사전에 계산된다. 예를 들어, 검색할 배열이 이면 중간 요소(m)는 이 된다. 이 경우 왼쪽 서브 배열()의 중간 요소는 이고 오른쪽 서브 배열()의 중간 요소는 이다. 균등 이진 검색은 두 인덱스 모두 과 같은 양만큼 다르므로  값을 저장한다. 검색 공간을 줄이기 위해 알고리즘은 중간 요소의 인덱스에서 이 변경 값을 더하거나 뺀다. 균등 이진 검색은 십진 컴퓨터와 같이 중간 지점을 계산하는 것이 비효율적인 시스템에서 더 빠를 수 있다.

### 지수 검색

[섬네일|upright=1.5|후속 이진 검색을 위한 상한을 찾는 [지수 검색의 시각화]]
지수 검색은 이진 검색을 무한정 목록으로 확장한다. 먼저 2의 거듭제곱이며 목표 값보다 큰 인덱스를 가진 첫 번째 요소를 찾는다. 그 후, 해당 인덱스를 상한으로 설정하고 이진 검색으로 전환한다. 검색은 이진 검색이 시작되기 전까지 \lfloor \log_2 x + 1\rfloor번의 반복을 수행하고 이진 검색은 최대 \lfloor \log_2 x \rfloor번의 반복을 수행하며, 여기서 x는 목표 값의 위치이다. 지수 검색은 유한 목록에서도 작동하지만, 목표 값이 배열의 시작 부분 근처에 있는 경우에만 이진 검색보다 개선된다.

### 보간 검색

[섬네일|upright=1.5|선형 보간을 사용한 [보간 검색의 시각화. 이 경우, 배열 내 목표 위치 추정치가 정확하므로 검색이 필요하지 않다. 다른 구현에서는 목표 위치를 추정하기 위해 다른 함수를 지정할 수 있다.]]
중간 지점을 계산하는 대신 보간 검색은 배열의 가장 낮은 요소와 가장 높은 요소, 그리고 배열의 길이를 고려하여 목표 값의 위치를 추정한다. 이는 많은 경우에 중간 지점이 최선의 추정치가 아니라는 전제에 기반한다. 예를 들어, 목표 값이 배열에서 가장 높은 요소에 가까울 경우, 배열의 끝 부분 근처에 위치할 가능성이 높다.

일반적인 보간 함수는 선형 보간법이다. A가 배열이고, L, R이 각각 하한과 상한이며, T가 목표 값이라면, 목표는 L과 R 사이의 (T - A_L) / (A_R - A_L) 지점에 있을 것으로 추정된다. 선형 보간을 사용하고 배열 요소의 분포가 균일하거나 거의 균일하면 보간 검색은 O(\log \log n)번의 비교를 수행한다.

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

### 분할 캐스케이딩

[섬네일|upright=1.8|[분할 캐스케이딩에서는 각 배열이 다른 배열의 모든 두 번째 요소에 대한 포인터를 가지고 있어, 모든 배열을 검색하는 데 하나의 이진 검색만 수행하면 된다.]]
분할 캐스케이딩은 여러 개의 정렬된 배열에서 동일한 요소를 이진 검색하는 속도를 높이는 기술이다. 각 배열을 개별적으로 검색하는 데는 O(k \log n) 시간이 필요하며, 여기서 k는 배열의 수이다. 분할 캐스케이딩은 각 배열에 각 요소와 다른 배열에서의 위치에 대한 특정 정보를 저장하여 이를 O(k + \log n)로 줄인다.

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

### 그래프로의 일반화
이진 검색은 특정 유형의 그래프에서 작동하도록 일반화되었으며, 여기서 목표 값은 배열 요소 대신 정점에 저장된다. 이진 탐색 트리는 그러한 일반화 중 하나이다. 트리의 정점(노드)을 질의할 때, 알고리즘은 정점이 목표라는 것을 알거나, 그렇지 않으면 목표가 어느 서브트리에 위치할지 알게 된다. 그러나 이는 다음과 같이 더 일반화될 수 있다. 무방향, 양의 가중치를 가진 그래프와 목표 정점이 주어졌을 때, 정점을 질의하면 그것이 목표와 같다는 것을 알거나, 질의된 정점에서 목표까지의 최단 경로에 있는 인접한 간선이 주어진다. 표준 이진 검색 알고리즘은 단순히 그래프가 경로인 경우이다. 유사하게, 이진 탐색 트리는 질의된 정점이 목표와 같지 않을 때 왼쪽 또는 오른쪽 서브트리로의 간선이 주어지는 경우이다. 모든 무방향, 양의 가중치를 가진 그래프에 대해 최악의 경우 O(\log n)번의 질의로 목표 정점을 찾는 알고리즘이 있다.

### 노이즈 이진 검색
섬네일|right|노이즈 이진 검색에서는 비교가 잘못될 확률이 존재한다.
노이즈 이진 검색 알고리즘은 배열의 요소를 신뢰할 수 있게 비교할 수 없는 경우를 해결한다. 각 요소 쌍에 대해 알고리즘이 잘못된 비교를 할 특정 확률이 있다. 노이즈 이진 검색은 주어진 확률로 목표의 올바른 위치를 찾을 수 있으며, 이 확률은 반환된 위치의 신뢰성을 제어한다. 모든 노이즈 이진 검색 절차는 평균적으로 최소한 (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는 절차가 잘못된 위치를 반환할 확률이다. 노이즈 이진 검색 문제는 답변이 틀릴 수 있는 레니-울람 게임의 한 경우로 간주될 수 있다. 이는 스무고개의 변형이다.

### 양자 이진 검색
고전 컴퓨터는 이진 검색을 수행할 때 최악의 경우 정확히 \lfloor \log_2 n + 1 \rfloor번의 반복으로 제한된다. 이진 검색을 위한 양자 알고리즘도 \log_2 n 질의(고전적 절차의 반복을 나타냄)의 비율로 제한되지만, 상수 계수가 1보다 작아 양자 컴퓨터에서 더 낮은 시간 복잡도를 제공한다. 어떤 정확한 양자 이진 검색 절차도(즉, 항상 올바른 결과를 산출하는 절차) 최악의 경우 최소 \frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n번의 질의를 필요로 한다. 여기서 \ln은 자연로그이다. 최악의 경우 4 \log_{605} n \approx 0.433 \log_2 n번의 질의로 실행되는 정확한 양자 이진 검색 절차가 있다. 이에 비해, 그로버 알고리즘은 정렬되지 않은 요소 목록을 검색하는 데 최적의 양자 알고리즘이며, O(\sqrt{n})번의 질의를 필요로 한다.

## 역사
더 빠른 검색을 위해 항목 목록을 정렬하는 아이디어는 고대부터 존재했다. 가장 초기의 알려진 예는 기원전 200년경 바빌로니아의 이나키비트-아누(Inakibit-Anu) 점토판이다. 이 점토판에는 약 500개의 육십진법 숫자와 그 곱셈 역원이 사전 편집 순서로 정렬되어 있어 특정 항목을 더 쉽게 찾을 수 있었다. 또한, 에게해 제도에서 첫 글자로 정렬된 여러 이름 목록이 발견되었다. 서기 1286년에 완성된 라틴어 사전인 카톨리콘 (1286)은 단순히 처음 몇 글자가 아니라 단어를 알파벳 순서로 정렬하는 규칙을 처음으로 기술한 저작이다.

1946년, 존 모클리는 컴퓨팅 분야의 중요하고 기초적인 대학 과정인 무어 스쿨 강의의 일부로 이진 검색을 처음 언급했다. 1957년, 윌리엄 웨슬리 피터슨은 보간 검색의 첫 번째 방법을 발표했다. 1960년까지 발표된 모든 이진 검색 알고리즘은 길이가 2의 거듭제곱보다 1 작은 배열에 대해서만 작동했다. 그러나 데릭 헨리 레머가 모든 배열에서 작동하는 이진 검색 알고리즘을 발표한 1960년 이후부터는 달라졌다. 1962년, 헤르만 보텐브루흐(Hermann Bottenbruch)는 알골 60 구현의 이진 검색을 발표했는데, 이는 등가 비교를 끝에 두어 평균 반복 횟수를 한 번 늘렸지만, 반복당 비교 횟수를 한 번으로 줄였다. 균등 이진 검색은 1971년 스탠퍼드 대학교의 A. K. 찬드라(A. K. Chandra)에 의해 개발되었다. 1986년, 버나드 샤젤과 레오니다스 J. 귀바스(Leonidas J. Guibas)는 계산기하학에서 수많은 검색 문제를 해결하기 위한 방법으로 분할 캐스케이딩을 도입했다.

## 구현 문제

존 벤틀리가 전문 프로그래머를 위한 강의에서 이진 검색을 문제로 냈을 때, 그는 90%가 몇 시간 동안 작업한 후에도 올바른 해결책을 제시하지 못했다는 것을 발견했다. 이는 주로 잘못된 구현이 드문 모서리 사례에서 실행되지 않거나 잘못된 답을 반환했기 때문이다. 1988년에 발표된 연구에 따르면, 정확한 코드는 20개 교과서 중 5개에서만 발견되었다. 더욱이, 벤틀리 자신이 1986년 저서 Programming Pearls에 발표한 이진 검색 구현에는 20년 이상 감지되지 않은 정수 오버플로 오류가 포함되어 있었다. 자바 프로그래밍 언어 라이브러리의 이진 검색 구현도 9년 이상 같은 오버플로 버그를 가지고 있었다.

실제 구현에서 인덱스를 나타내는 변수는 종종 고정 크기(정수)이며, 이는 매우 큰 배열에서 산술 오버플로를 초래할 수 있다. 범위의 중간 지점이 \frac{L+R}{2}로 계산되면, L과 R이 중간 지점을 저장하는 데 사용되는 데이터 유형의 정수 범위 내에 있더라도 L+R의 값이 해당 범위를 초과할 수 있다. L과 R이 음수가 아닌 경우, 중간 지점을 L+\frac{R-L}{2}로 계산하여 이를 피할 수 있다.

루프의 종료 조건이 올바르게 정의되지 않으면 무한 루프가 발생할 수 있다. L이 R을 초과하면 검색이 실패했으므로 검색 실패를 전달해야 한다. 또한, 목표 요소를 찾았을 때 루프를 종료해야 하며, 이 검사가 끝으로 이동된 구현의 경우 검색이 성공했는지 실패했는지에 대한 검사가 마지막에 있어야 한다. 벤틀리는 이진 검색을 잘못 구현한 대부분의 프로그래머가 종료 조건을 정의하는 데 오류를 범했다고 밝혔다.

## 라이브러리 지원
많은 언어의 표준 라이브러리에는 이진 검색 루틴이 포함되어 있다.

* C는 표준 라이브러리에 `bsearch()` 함수를 제공하며, 이는 일반적으로 이진 검색을 통해 구현되지만 공식 표준은 이를 요구하지 않는다.
* C++의 표준 라이브러리는 `binary_search()`, `lower_bound()`, `upper_bound()` 및 `equal_range()` 함수를 제공한다. C++20 `std::ranges` 라이브러리를 사용하면 `std::ranges::binary_search()`로 범위에 적용할 수 있다.
* D의 표준 라이브러리 Phobos는 `std.range` 모듈에서 `SortedRange` 유형(`sort()` 및 `assumeSorted()` 함수가 반환)을 제공하며, `contains()`, `equaleRange()`, `lowerBound()` 및 `trisect()` 메서드는 무작위 접근을 제공하는 범위에 대해 기본적으로 이진 검색 기술을 사용한다.
* 코볼은 코볼 정렬 테이블에서 이진 검색을 수행하기 위해 `SEARCH ALL` 동사를 제공한다.
* Go의 `sort` 표준 라이브러리 패키지에는 일반 이진 검색을 구현하는 `Search`, `SearchInts`, `SearchFloat64s`, `SearchStrings` 함수와 함께 정수, 부동소수점 숫자 및 문자열 슬라이스 검색을 위한 특정 구현이 포함되어 있다.
* 자바는 표준 `java.util` 패키지의  및  클래스에서 자바 배열 및 `List`에 대해 이진 검색을 수행하기 위한 오버로드된 `binarySearch()` 정적 메서드 세트를 제공한다.
* 마이크로소프트의 닷넷 프레임워크 2.0은 컬렉션 기본 클래스에 이진 검색 알고리즘의 정적 제네릭 버전을 제공한다. 예를 들어, `System.Array`의 `BinarySearch<T>(T[] array, T value)` 메서드가 있다.
* 오브젝티브-C의 경우, 코코아 프레임워크는 Mac OS X 10.6+에서  메서드를 제공한다. 애플의 Core Foundation C 프레임워크에는 `[https://developer.apple.com/library/mac/documentation/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/c/func/CFArrayBSearchValues CFArrayBSearchValues()]` 함수도 포함되어 있다.
* 파이썬은 각 삽입 후에 목록을 정렬할 필요 없이 목록을 정렬된 상태로 유지하는 `bisect` 모듈을 제공한다.
* 루비의 Array 클래스에는 내장된 근사 일치 기능을 갖춘 `bsearch` 메서드가 포함되어 있다.
* 러스트의 슬라이스 기본형은 `binary_search()`, `binary_search_by()`, `binary_search_by_key()` 및 `partition_point()`를 제공한다.

## 같이 보기
*  – 실수 방정식 풀이에 사용되는 동일한 아이디어
* 

## 내용주 및 각주
### 내용주

### 각주

### 출처

## 외부 링크

* NIST 알고리즘 및 자료 구조 사전: 이진 검색
* C에서 다양한 이진 검색 구현의 비교 및 벤치마크 

분류:검색 알고리즘
분류:2