# 이진 검색보다 빠르게 만들 수 있음 > Clean Markdown view of GeekNews topic #29069. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=29069](https://news.hada.io/topic?id=29069) - GeekNews Markdown: [https://news.hada.io/topic/29069.md](https://news.hada.io/topic/29069.md) - Type: GN+ - Author: [xguru](https://news.hada.io/@xguru) - Published: 2026-05-01T19:53:34+09:00 - Updated: 2026-05-01T19:53:34+09:00 - Original source: [lemire.me](https://lemire.me/blog/2026/04/27/you-can-beat-the-binary-search/) - Points: 1 - Comments: 1 ## Topic Body - 정렬 배열의 멤버십 검사는 교과서적 **이진 검색**보다 더 빠르게 만들 수 있으며, SIMD Quad는 모든 측정 조건에서 `std::binary_search`보다 빨랐음 - **SIMD Quad**는 16비트 부호 없는 정수 정렬 배열을 16개 원소 블록으로 나누고, 블록 경계에서는 4진 보간 검색을, 블록 내부에서는 SIMD 병렬 비교를 수행함 - 최신 64비트 ARM과 x64(Intel/AMD)는 한 명령으로 16비트 정수 8개를 비교할 수 있어, 한 번에 값 하나만 검사하는 이진 검색 구조를 그대로 따를 필요가 줄어듦 - 벤치마크는 크기 2~4096의 정렬 배열 100,000개와 멤버십 질의 1,000만 번으로 수행됐으며, **cold** 모드는 캐시 미스, **warm** 모드는 캐시 히트를 시뮬레이션함 - Intel에서는 warm 캐시에서 SIMD Quad가 이진 검색보다 2배 이상 빨랐고, Apple에서는 cold 캐시에서 2배 이상 빨랐으며, Intel 큰 배열 cold 캐시에서는 4진 접근이 메모리 수준 병렬성을 더 잘 활용함 --- ### 정렬 배열 멤버십 검사의 병목 - 정렬된 배열에서 값 존재 여부를 확인하는 가장 단순한 방법은 값을 하나씩 훑는 **선형 검색**이며, C++에서는 `std::find`로 같은 효과를 낼 수 있음 - 큰 배열에서는 **이진 검색**이 더 빠르며, 검색 구간의 가운데 값을 기준으로 상·하반을 버리는 과정을 값 발견 또는 빈 구간 도달까지 반복함 - C++의 `std::binary_search`는 값 존재 여부를 불리언으로 반환함 - Roaring Bitmap 형식은 크기 1~4096의 16비트 정수 배열을 사용하며, 값 존재 여부 확인에 이진 검색을 사용함 ### SIMD Quad의 출발점 - 최신 프로세서는 대부분 데이터 병렬 명령어인 **SIMD**를 갖고 있으며, 64비트 ARM과 x64(Intel/AMD)는 한 명령으로 16비트 정수 8개를 대상 값과 비교할 수 있음 - 이 특성 때문에 이진 검색을 8개보다 작은 블록까지 계속 내려갈 필요가 없고, 16개 이상의 원소도 저렴하게 비교할 수 있음 - 이진 검색은 한 번에 값 하나를 검사하지만, 최근 프로세서는 한 번에 여러 값을 로드하고 검사할 수 있으며 **메모리 수준 병렬성**도 좋음 - 배열을 반으로 나누는 대신 4분할하는 **4진 검색**을 시도할 수 있으며, 명령어 수는 약간 늘어도 병목이 명령어 수가 아닐 가능성이 큼 ### SIMD Quad 알고리듬 구조 - SIMD Quad는 16비트 부호 없는 정수의 정렬 배열을 위한 검색 알고리듬으로, **4진 보간 검색**과 SIMD를 결합함 - 배열을 16개 원소의 고정 크기 블록으로 나누고, 마지막 블록은 예외가 될 수 있음 - 각 블록의 마지막 원소를 보간 키로 사용해 대상 값이 있을 가능성이 높은 단일 블록으로 범위를 좁힌 뒤, 그 블록의 16개 원소를 SIMD로 동시에 검사함 - 핵심 흐름은 블록 경계에서 보간 검색으로 비교 횟수를 줄이고, 블록 내부에서 SIMD로 병렬 비교를 수행하는 계층형 검색임 - 동작 단계는 다음과 같음 - 원소 수가 16개보다 적으면 전체를 단순 선형 검색함 - `cardinality` 크기 배열을 16개 연속 원소 블록으로 나누고, 전체 블록 수는 `num_blocks = cardinality / 16`임 - 위치 `16-1`, `32-1` 등의 블록 마지막 원소를 키로 사용해 현재 검색 범위의 1/4 지점들을 대상 `pos`와 비교하고 `base`를 조정함 - 보간 결과에 따라 적절한 블록 인덱스 `lo`를 선택함 - 유효한 블록이면 ARM에서는 NEON, x64에서는 SSE2로 16개 원소를 로드해 대상 값과 병렬 동등 비교를 수행하고, 일치가 있으면 `true`를 반환함 - 전체 16개 블록에 포함되지 않는 나머지 원소는 선형 검색함 ### 벤치마크 방식 - 벤치마크는 배열 크기 2~4096 각각에 대해 16비트 부호 없는 정수의 정렬 배열 100,000개를 생성함 - 각 크기마다 두 가지 모드로 멤버십 질의 1,000만 번을 수행함 - **cold** 모드: 각 질의가 다른 배열을 검색해 캐시 미스를 시뮬레이션함 - **warm** 모드: 질의를 배열별로 묶고 같은 배열을 100번 연속 검색해 캐시 히트를 시뮬레이션함 - 측정 대상은 평균 질의 시간이며, 비교 알고리듬은 선형 검색(`std::find`), 이진 검색(`std::binary_search`), SIMD Quad임 - 측정 시스템은 Apple M4와 Apple LLVM, Intel Emerald Rapids 프로세서와 GCC임 ### 측정 결과 - 선형 검색과 이진 검색 비교에서는 배열이 커지면 이진 검색이 선형 검색을 이김 - cold 캐시에서는 더 많은 데이터 접근으로 캐시 실패가 늘어나기 때문에 선형 검색이 상대적으로 더 불리함 - 이진 검색이 선형 검색보다 전반적으로 우세한 뒤, SIMD Quad와 비교됨 - Intel과 Apple 플랫폼의 결과는 뚜렷하게 달랐음 - Intel 플랫폼에서는 warm 캐시에서 SIMD Quad가 이진 검색보다 2배 이상 빠름 - Intel 플랫폼의 cold 캐시에서는 이득이 더 작음 - Apple 플랫폼에서는 반대로 cold 캐시에서 SIMD Quad가 2배 이상 빠르고, warm 캐시에서는 이득이 더 제한적임 - 모든 경우에서 SIMD Quad는 이진 검색보다 빨랐음 - SIMD 부분은 특수 명령어로 작업을 줄이며, 명령어와 분기가 더 적어 속도 향상을 이해하기 쉬움 ### 4진 검색의 효과 - SIMD 최적화는 유지하되 4진 보간 검색을 표준 이진 검색으로 바꾼 **SIMD binary** 버전도 비교함 - Apple 플랫폼에서는 4진 접근의 효과가 작았음 - Intel 플랫폼에서는 큰 배열의 cold 캐시 상황에서 4진 접근이 의미 있는 최적화였음 - Intel 서버에서는 4진 검색이 메모리 수준 병렬성을 더 잘 활용했음 ### 구현 핵심 - `simd_quad` 함수는 `uint16_t` 배열, 원소 수 `cardinality`, 찾을 값 `pos`를 받아 불리언을 반환함 - `gap`은 16으로 고정되어 있으며, `cardinality < gap`이면 단순 반복문으로 값을 찾음 - 블록 검색 루프는 `n > 3` 동안 1/4, 2/4, 3/4 지점의 블록 마지막 값을 읽어 `pos`보다 작은지 비교하고, 세 비교 결과의 합으로 `base`를 이동함 - 이후 `n > 1` 동안 절반 기준 비교를 수행해 남은 범위를 줄이고, 마지막으로 `lo` 블록을 선택함 - 선택된 블록은 ARM NEON의 `vceqq_u16` 또는 x64 SSE2의 `_mm_cmpeq_epi16`로 16개 원소를 두 묶음으로 비교함 - 나머지 원소 구간은 `v >= pos`가 되는 지점에서 `v == pos` 여부를 반환하고, 끝까지 없으면 `false`를 반환함 ### 결론과 자료 - 교과서적 이진 검색은 괜찮은 알고리듬이지만, 실제 성능에 의미 있는 방식으로 더 빠르게 만들 수 있음 - 표준 알고리듬은 오늘날 컴퓨터의 높은 병렬성을 전제로 설계되지 않은 경우가 많음 - SIMD Quad는 메모리 수준 병렬성과 데이터 병렬성을 모두 활용하려는 접근임 - 더 나은 알고리듬도 가능할 수 있으며, 더 창의적인 접근이 필요함 - [소스 코드]() - [Faster intersections between sorted arrays with shotgun]() ## Comments ### Comment 56660 - Author: neo - Created: 2026-05-01T19:53:35+09:00 - Points: 1 ###### [Hacker News 의견들](https://news.ycombinator.com/item?id=47924912) - Daniel Lemire가 말한 **저수준 하드웨어 최적화**와는 별개로, 이진 탐색이나 그 구현 변형이 최선인 경우는 데이터가 정렬/단조라는 사실 외에 아무것도 모를 때뿐임 데이터 분포에 대한 사전 정보가 있으면 그 정보를 써서 훨씬 더 빠른 알고리즘을 만들 수 있음. 종이 사전에서 사람이 순수한 이진 탐색보다 더 빨리 적당한 페이지 묶음으로 이동하는 것이 예시임 수학적으로 정렬 리스트 검색은 닫힌 루프 제어 알고리즘으로 **단조 함수의 역함수**를 찾는 일에 가깝고, 비용 함수를 만들어 경사 하강법이나 가속 변형을 쓸 수도 있음. 더 일반적으로는 지나치게 추상화된 표현의 해법을 가져오기보다, 풀려는 특정 문제에 대한 정보를 더 쓰는 편이 항상 더 효율적이며, 하드웨어를 더 잘 써서 얻는 상수배 개선보다 훨씬 큰 확장 가능한 속도 향상을 줄 수 있음 - 이진 탐색에 꽤 머리를 써봤지만, 이 구현보다 나은 걸 못 찾았음: [https://github.com/protocolbuffers/protobuf/blob/44025909eb7...]() 1. 조밀한 리스트인지 O(1)로 확인 2. 상한 확인 3. 반복 횟수가 고정된 이진 탐색 고정 반복 횟수는 **분기 예측기**에 좋고, 핵심 루프도 대상 하드웨어에 맞게 곱셈을 피하며 꽤 빡빡하게 최적화돼 있음. 더 영리하게 만들려는 시도는 루프를 악화시켰고 이득을 못 냈음. 구조체 배열 형식에 크기가 12이고, 대체로 N이 작아서 어렵기도 함 - 트립(treap)에 관한 글을 읽은 기억이 있는데, 트리 균형을 맞추는 대신 가중치를 써서 **허프만 인코딩**처럼 탐색 깊이를 조정하고, 접근 빈도가 다른 경우 평균 접근 시간을 줄이는 방식이었음 북마크를 안 해둬서 1년에 두 번쯤 다시 찾고 있음. 전설에 따르면 아직도 찾는 중임 - 맞지만, 핵심은 데이터를 더 알 수 없는 경우가 많다는 것임 그래서 데이터베이스에서는 **B-트리**가 표준임. 데이터는 무엇이든 될 수 있고, 새 행을 대량으로 가져오면 특성이 언제든 크게 바뀔 수 있음 경사 하강법 같은 방식으로 조회를 가속하는 알고리즘을 만들 수는 있지만, B-트리는 이미 매우 빠르고 최악 성능과 I/O 요구량 예측 가능성, 범위 스캔, 정렬 순회, 접두 조건 지원 같은 장점도 많음 특정 데이터 분포에 더 효율적인 조회 알고리즘은 만들 수 있지만, 중요한 속성을 잃는 경우가 많음. 다른 알고리즘이 더 가까운 초기 추정을 내더라도 마지막 항목을 찾는 데 느릴 수 있고, 평균은 빨라도 최악 성능이 너무 나빠서 못 쓸 수도 있음 종이 사전에서도 첫 추정 이후에는 거의 이진 탐색을 썼고, 그 초기 추정으로 줄어드는 단계는 몇 번뿐임. 적당한 페이지 묶음에 도달한 뒤에는 필요한 것보다 선형적으로 훑는 편인데, 엄격한 이진 탐색을 하면 더 빠를 수도 있지만 페이지 넘기는 시간과도 균형을 맞춰야 함 - “풀려는 특정 문제에 대한 정보를 더 쓰는 것이 더 효율적”이라는 말은 뻔하면서도 깊음. 이미 가진 정보가 많을수록, 이미 가진 정보가 많은 셈임 - Fritz Henglein이 빠른 정렬/그룹화에 대해 흥미로운 작업을 했음. 핵심 논문은 **Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time**[1]로 보임 Ed Kmett은 그 아이디어를 Haskell용 **discrimination**[2] 라이브러리로 다듬었고, 관련 기술 발표[3]도 매우 흥미로움 [1]: [https://dl.acm.org/doi/epdf/10.1145/1411203.1411220]() [2]: [https://hackage.haskell.org/package/discrimination]() [3]: [https://www.youtube.com/watch?v=cB8DapKQz-I]() - “4분 탐색”은 결국 이진 탐색 루프를 한 단계 펼친 것 아닌가? 항목이 있는 구간을 찾으려면 비교 횟수는 대략 비슷하고, 한 번에 2개가 아니라 4개씩 처리하는 것처럼 보임. **루프 펼치기**로도 같은 효과가 날 것 같음 - 그보다 더 까다로움. 현대 프로세서는 **추측 실행**을 해서 비교 결과를 예측하고, 틀렸다는 걸 알거나 내부 한계에 닿을 때까지 한쪽 분기를 계속 진행함. 틀리면 추측 작업을 버리고 몇 사이클 페널티를 낸 뒤 다른 시작점에서 다시 함 사실상 프로세서 관점에서는 모든 루프가 이미 어느 정도 펼쳐져 있고, 루프 자체의 작은 오버헤드만 남음. 이진 탐색에서 주된 비용은 메모리나 캐시에서 데이터를 가져오는 것이므로, 실제 싸움은 나중에 필요할 데이터를 최대한 일찍 요청하게 만들어 도착을 덜 기다리는 것임 4분 탐색 같은 알고리즘의 차이는 각 분기의 한쪽만 깊게 미리 가져오는 대신, 가능한 모든 경우를 얕게 **프리페치**한다는 데 있음. 결국 필요할 프리페치는 반드시 발행되고, 실제 실행 경로에서 쓰지 않을 데이터에 대역폭을 조금 덜 쓰게 됨 검색 알고리즘의 실제 성능을 예측하려면 “비교 횟수”는 거의 쓸모없는 지표임. 병목은 비교를 얼마나 많이 할 수 있느냐가 아니라 메모리와 캐시 대역폭을 최대한 활용하느냐에 달려 있음. 현대 프로세서의 분기 동작을 내부까지 고려한다면 루프 펼치기로 볼 수도 있음 - 이건 루프를 조금 펼친 것으로 볼 수 있음. 성능이 좋아지는 이유는 명령 수나 메모리 읽기를 크게 줄여서가 아니라, 연산 간 **의존성**을 완화해 순수 직렬 실행을 피하기 때문임. 분기의 양쪽을 추측 실행하는 것과 비슷하게 볼 수도 있음 - 4분 탐색은 사실상 현재 반복의 비교와 동시에 다음 반복에서 가능할 두 비교를 함께 수행함. 단순한 **루프 펼치기**보다는 조금 더 복잡함 어쨌든 두 탐색 모두 상수가 다른 O(log N)임. 알고리즘 수업에서는 상수가 별로 중요하지 않지만 현실에서는 꽤 크게 작용할 수 있음 - 어느 정도 맞지만, 펼쳐진 단계 사이의 **데이터 의존성**도 제거하고 있음 - 프로세서는 우리가 순진하게 생각하는 방식으로 동작하지 않기 때문임 - 최근에 **지수 탐색**[2]에 대해서도 글[1]을 썼음. 찾는 원소들 자체가 정렬된 상태로 배열에서 반복적으로 이진 탐색해야 할 때 쓸 수 있는 알고리즘이고, 우리 작업 부하에서는 8배 속도 향상이 나왔음 [1] [https://lalitm.com/post/exponential-search/]() [2] [https://en.wikipedia.org/wiki/Exponential_search]() - 지수 탐색은 순차 ID로 리소스를 주소 지정하는 **REST API**에서 마지막 ID가 필요하지만 전용 엔드포인트가 없을 때 유용함 HEAD /users/1 -> 200 OK HEAD /users/2 -> 200 OK HEAD /users/4 -> 200 OK ... HEAD /users/2048 -> 200 OK HEAD /users/4096 -> 404 Not Found 그런 다음 2048과 4096 사이를 이진 탐색하면 가장 최근 사용자와 부수적으로 사용자 수를 찾을 수 있음. 경쟁 SaaS 회사를 조사할 때 알면 좋은 정보임 - CPU는 항상 **캐시 라인** 전체, 보통 64바이트를 한 번에 접근하니 캐시 라인 전체를 검색하는 편이 낫겠음. 데이터가 CPU 안에 올라온 뒤에는 사실상 공짜에 가까움 그래서 “이진” 탐색에서 가운데 캐시 라인의 모든 값을 검사하고, 일치하는 값이 없으면 왼쪽/오른쪽으로 가는 방식을 시도해보고 싶음. 캐시 라인 검색은 512비트 SIMD 명령 하나로 가능함. 캐시 라인 64바이트는 16비트 정수 32개이므로, 단순 이진 탐색보다 거의 32배 빠를 수도 있고, 적어도 메모리 접근은 32배 줄어들어 현실적인 프로그램 대부분에서 지배적일 것임 - 이진 탐색 트리, 즉 정렬 벡터의 위쪽 캐시 라인에서 목표값을 찾을 가능성은 낮음. 대신 라인 안의 추가 데이터를 이용해 탐색 범위를 줄이는 편이 좋고, 그러면 **B-트리**나 B+트리로 이어짐 4바이트 키와 4바이트 자식 포인터, 또는 배열 인덱스를 쓰면 내부 노드는 키 7개, 자식 포인터 8개, 다음 포인터 1개로 64바이트 캐시 라인을 꽉 채울 수 있음. 100만 항목에서 트리 깊이는 약 20에서 약 7로 줄고, 위쪽 몇 단계는 캐시에 남아 있을 가능성이 큼 조금 고민하면 SIMD로 B-트리 노드 내부 검색을 빠르게 할 수 있지만, 데이터 의존성이 매우 큼 - 더 작은 배열이라면 끝에 **센티널 값**을 둔 선형 탐색은 이미 이기기 어려움. 다만 이 주장이 애매한 이유는 “작다”가 너무 흐릿한 조건이라 체감하기 어렵다는 데 있음 - 그건 사실이 아님. 이 글의 훌륭한 벤치마크를 보면 **선형 탐색**은 대략 200~400개 원소 부근에서 뒤처짐 전반적으로 이 글은 마음에 듦. 평소 궁금했던 점을 유용한 제거 실험까지 곁들여 완벽하게 탐구했음 - 이 글이 다루는 내용은 그게 아님 - 작은 배열, 16~32개 항목에서 검색 실험을 조금 해봤는데 이진 탐색은 분기가 많아서 최악의 방법 중 하나였음. 작은 배열에서 가장 빠른 방법은 **분기 없는 선형 탐색**이었음 루프를 중간에 끊지 않고 모든 원소를 훑는 방식임. 예를 들어 배열에 어떤 수가 있는지 알고 싶다면 모든 항목의 검사 결과를 논리 OR로 합침. SIMD는 쓰지 않았지만, 작은 배열에서는 분기가 매우 비싸서 분기 없이 모든 원소를 그냥 검사하는 편이 더 빠름 - 프리페처가 좋아하는 접근 패턴이라 더 빠른 건지 궁금함 - 알고리즘 설명이 조금 헷갈렸음 **SIMD** 부분은 마지막 단계, 즉 마지막 16개 원소를 검색할 때만 쓰임 4분 탐색 부분은 3개 지점을 검사해서 4개 경로를 만드는 것이지만, 단순히 올바른 키가 아니라 올바른 블록을 찾고 있음 세부가 흥미로운데, 작성자는 각 블록의 마지막 원소를 4분 탐색에 사용함. 첫 원소를 쓰거나 임의의 원소를 쓰면 알고리즘이 어떻게 바뀔지 궁금함 - 여기의 핵심 직관인 **SIMD 다중 비교**는 마지막 단계보다 더 큰 규모에도 쓸 수 있어 보임 개요는 이렇다: a) gather로 균등 간격 16곳에서 여러 원소를 가져옴 b) SIMD 명령으로 병렬 비교 c) 올바른 블록에 집중 d) 블록이 작으면 선형 탐색으로 전환하고, 아니면 gather/비교 주기를 반복함 gather 명령은 비연속 메모리에서 읽고, 이진 탐색이라면 필요하지 않을 만큼 더 많이 읽긴 함. 그래도 다방향 비교가 가능해지고 이진 탐색 4단계를 접을 수 있다면 큰 테이블에서는 이길 수 있을 듯함 모든 자료형에서 완전한 16방향 비교가 가능한 것도 아님. float64 검색은 AVX-512에서도 8방향 비교로 제한되지만, int32와 float32는 16방향 비교가 가능함 - **gather**는 극도로 느림. 효율을 노리는 사람이라면 gather를 피할 것임 gather 기반 방식보다 이진 탐색이 실제로 더 빠를 가능성이 높다고 봄 - 고전적인 컴퓨터 과학 알고리즘은 사실상 병렬성이 없는 CPU를 대상으로 “설계”된 셈임. 여러 코어, Hyper-threading, SIMD 명령 같은 병렬성이 없고, 모든 메모리 접근 시간이 같아서 L1/L2/L3 캐시 지연 같은 개념도 없으며, 일반적/무작위 데이터를 다룬다는 가정임 이 가정 중 하나라도 벗어나면 성능을 높일 수 있는 조정이 많이 생김 고전 알고리즘은 특정 데이터 형태나 특정 CPU의 특성/기능을 더 알게 된 뒤 더 최적화된 해법을 개발하기 위한 매우 좋은 출발점을 제공함 최적화의 뾰족한 끝까지 가면 보통 데이터가 메모리에 어떻게 저장되고 접근되는지, 그리고 이를 개선하는 변경이 이후 단계에 해를 끼치지 않는지를 보게 됨. 오래전 직장에서 누군가 코드의 특정 부분을 너무 오래 최적화했는데, 그 최적화 때문에 나중에 필요한 많은 정보가 캐시에서 밀려나 전체 애플리케이션은 더 느려진 일이 있었음 이는 아마 Rob Pike의 프로그래밍 5번째 규칙, 다시 말해 _The Mythical Man Month_에서 Fred Brooks가 한 말을 재진술한 것에 가까움. 참고: [https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...]() - 십대 때 주말 내내, 이진 탐색이 매 단계 탐색 공간을 절반으로 줄여서 좋다면 **삼진 탐색**은 3분의 1씩 줄이니 더 낫지 않을까 생각했음 가운데 값 하나만 비교하는 대신 1/3 지점 값을 비교하고, 너무 낮으면 2/3 지점 값을 비교하는 방식임 하지만 각 단계에서 이진 탐색의 1/2 대신 1/3로 줄이는 반면, 비교는 평균 3/2배 한다고 생각해서 결국 같다고 봤음 수정: zamadatix 답변을 보니 실제로는 2/3의 경우 비교를 2번 해야 하므로 평균 5/3배임 - 이 삼진 접근은 실제로 단계당 평균 비교 횟수가 3/2가 아님 첫 1/3: 비교 1번 둘째 1/3: 비교 2번 셋째 1/3: 비교 2번 (1+2+2)/3 = 평균 5/3번 비교임. “비교를 1번 하거나 2번 한다”는 느낌 때문에 50%로 착각하기 쉽지만, 실제로는 첫 비교에서 걸릴 확률이 1/3이고, 2번 비교할 확률이 2/3임 그래서 총 평균 비교 횟수에서 삼진 탐색이 아주 조금 더 나쁨을 보일 수 있음: 5/3*Log_3[n] = 1.052... * Log_2[n] 즉 단계 수는 줄지만 끝까지 가기 위해 평균적으로 더 많은 비교를 하게 됨. 이건 이런 유형의 모든 탐색, 즉 분할 수가 2보다 큰 경우에 대체로 성립함. 물론 찾는 값이 균등 분포하고 연산 비용이 이상화돼 있다는 몇 가지 가정이 있고, 바로 이 지점에서 본문 글의 논의가 들어옴 - 알고 보니 십대 시절의 그 생각에도 뭔가가 있었음 이진 탐색 알고리즘의 삼진 버전으로서는 아님. 그건 실제 삼진 탐색이 아니라 치우친 이진 탐색에 가깝기 때문임. 비교는 본질적으로 이진이므로, 비교를 포함하는 탐색 알고리즘은 모두 일종의 이진 탐색이고, 가운데 원소가 아닌 선택은 알고리즘 복잡도 측면에서 덜 효율적임. 다만 실제 하드웨어에서는 어떤 조건에서 더 나을 수도 있음. 진짜 삼진 탐색을 하려면 기본 연산으로 **3방향 비교**가 필요함 흥미로워지는 지점은 “기수 효율”[1]을 고려할 때임. 최선의 선택은 e에 가장 가까운 자연수인 3임. 트리 탐색과도 관련이 있어서, 삼진 트리가 이진 트리보다 나을 수 있음 [1] [https://en.wikipedia.org/wiki/Optimal_radix_choice]() - 빠른 탐색이 불가능한 디스크 같은 곳에서는 예를 들어 **128방향 B-트리**를 쓸 수 있음. 키 128개를 가져오는 비용은 1개를 가져오는 것보다 크게 비싸지 않지만, 추가로 7번의 가져오기를 줄여줌 - 그 다음에는 삼진 비교기를 포함한 CPU를 상상했나? - 십대 시절 이후 CPU는 실행 폭과 벡터 기능 양쪽에서 극적으로 넓어졌음. 처리량이 늘면서, 의존성 사슬을 줄이기 위해 연산을 더 태우는 쪽으로 균형이 이동함 그래서 그 아이디어가 당시 CPU에서는 실현성이 없었지만 지금 CPU에서는 더 가능성이 높아졌을 수 있음