· 개발

이진 탐색의 삽입 위치: bisect, lower_bound, binarySearch는 무엇을 돌려주나

값이 없거나 중복될 때 Python bisect, C++ lower_bound, Java Arrays.binarySearch가 돌려주는 위치와 각 API의 전제 조건을 공식 문서와 C++ 표준을 따라 비교했습니다.

개발알고리즘

이진 탐색은 값을 찾는 방법으로 배우지만, 코드를 작성하다 보면 다른 질문도 자주 만납니다. 이 값이 들어간다면 몇 번째 자리인가? Python, C++, Java 모두 이진 탐색 API를 제공하지만 반환값의 뜻은 서로 다릅니다.

다음 배열을 기준으로 비교해 보겠습니다.

a = [1, 2, 4, 5, 5, 6]

삽입 위치는 원소가 아니라 경계다

원소가 6개인 배열에는 0부터 6까지 7개의 삽입 위치가 있습니다. 값 5를 기준으로는 두 경계를 생각할 수 있습니다.

  • 5보다 작은 것 | 5 이상인 것 → 3
  • 5 이하인 것 | 5보다 큰 것 → 5

첫 번째 경계는 첫 번째 5의 앞이고, 두 번째 경계는 마지막 5의 뒤입니다. 값이 없으면 두 경계가 같은 자리로 모입니다. 위 배열에서 3의 삽입 위치는 2입니다.

Python: bisect_left와 bisect_right

Python 공식 문서가 정의하는 것이 바로 이 두 경계입니다.

import bisect

a = [1, 2, 4, 5, 5, 6]
bisect.bisect_left(a, 5)   # 3
bisect.bisect_right(a, 5)  # 5
bisect.bisect_left(a, 3)   # 2

이 결과는 Python 3.14.7에서 직접 확인했습니다.

두 함수는 __lt__만 호출하고 __eq__는 호출하지 않습니다. 따라서 반환된 위치만으로는 값이 실제로 있는지 알 수 없습니다. 값의 존재를 확인하려면 bisect_left의 결과가 배열 범위 안에 있는지, 해당 원소가 찾는 값과 같은지를 따로 검사해야 합니다.

bisect_left와 bisect_right의 key 인수는 Python 3.10에서 추가됐습니다. key 함수는 배열 원소에 적용되지만 찾는 값 x에는 적용되지 않습니다.

입력 목록은 정렬되어 있어야 합니다. 또한 공식 문서는 bisect 함수가 스레드 안전하지 않다고 명시합니다. 같은 시퀀스를 여러 스레드가 동시에 검색하거나 검색 도중 다른 스레드가 변경하면 결과가 정의되지 않습니다.

C++: lower_bound와 upper_bound

C++의 lower_bound는 bisect_left와 같은 경계를, upper_bound는 bisect_right와 같은 경계를 반환합니다.

std::vector<int> a{1, 2, 4, 5, 5, 6};

std::lower_bound(a.begin(), a.end(), 5) - a.begin();  // 3
std::upper_bound(a.begin(), a.end(), 5) - a.begin();  // 5

이 결과는 Apple clang 17과 -std=c++17로 실행해 확인했습니다.

C++ 표준이 요구하는 조건은 전체 범위의 정렬이 아니라 **분할(partitioned)**입니다. e < value인 원소가 그렇지 않은 원소보다 모두 앞에 있으면 됩니다. 정렬되지 않은 범위라도 특정 검색값에 대해서는 이 조건을 만족할 수 있습니다. 조건이 깨졌을 때의 동작은 cppreference에서 정의되지 않은 동작으로 설명합니다.

Java: Arrays.binarySearch

Java는 키를 찾으면 해당 인덱스를 반환합니다. 찾지 못하면 다음 식을 반환합니다.

-(삽입 위치) - 1

삽입 위치는 키보다 큰 첫 번째 원소의 인덱스이며, 그런 원소가 없으면 배열 길이입니다. 위 배열에서 3의 삽입 위치는 2이므로 계약에 따른 반환값은 -3입니다. 반환값이 r이라면 -(r + 1)로 삽입 위치를 복원할 수 있습니다.

중복값은 주의해야 합니다. Javadoc은 같은 값이 여러 개일 때 어느 인덱스가 반환될지 보장하지 않습니다. 5를 찾으면 3이나 4가 반환될 수 있습니다. 따라서 Arrays.binarySearch는 lower_bound가 아닙니다. 첫 번째 위치가 필요하다면 경계를 구하는 탐색을 별도로 구현해야 합니다.

Java 배열은 검색 전에 정렬되어 있어야 하며, 그렇지 않으면 결과가 정의되지 않습니다.

반환값 비교

API 값이 있을 때 값이 없을 때 중복값 입력 조건
Python bisect_left 첫 번째 위치 삽입 위치 가장 왼쪽 앞 정렬
Python bisect_right 마지막 위치 다음 삽입 위치 가장 오른쪽 뒤 정렬
C++ lower_bound 첫 번째 위치 삽입 위치 가장 왼쪽 앞 검색 조건에 따라 분할
C++ upper_bound 마지막 위치 다음 삽입 위치 가장 오른쪽 뒤 검색 조건에 따라 분할
Java binarySearch 일치하는 인덱스 -(삽입 위치) - 1 어느 위치인지 보장 없음 정렬

세 API 모두 입력 조건을 호출 전에 검사해 주지는 않습니다. Python과 Java는 정렬된 입력을, C++은 검색에 사용하는 비교식에 따라 분할된 범위를 요구합니다.

정렬 알고리즘이 같은 값의 순서를 어떻게 다루는지는 안정 정렬 글에서 확인할 수 있습니다.

블로그로