이진 탐색의 불변식: 탐색 구간·중간값·종료 조건

이진 탐색은 탐색 구간과 종료 조건을 어떻게 일관되게 정하나요?

이진 탐색은 정렬된 배열에서 답이 있을 구간을 절반씩 줄이는 방법입니다. 구간의 오른쪽 끝을 포함할지부터 정하면 이동과 종료 조건을 일관되게 쓸 수 있습니다.

[1,3,3,7]에서 3 이상인 첫 위치는 인덱스 1입니다. 아무 3 하나를 찾는 것과 첫 위치를 찾는 것은 서로 다른 목표입니다.

적용 조건·범위: 원본은 정렬을 수행하거나 정렬 여부를 검사하지 않습니다. 예를 들어 [3,1,2]에서 3을 찾으면 중간 1보다 크다는 이유로 오른쪽만 보고 null을 반환할 수 있습니다. 오름차순으로 정렬된 숫자 배열을 준비해야 합니다. 문자열 순서가 적용되는 기본 sort()와 혼동하지 말고, 숫자 정렬에는 sort((a,b) => a-b)처럼 같은 순서 기준을 사용합니다. 탐색 중 배열도 바꾸지 않습니다.

본문 근거: C++ 표준 초안 — lower_bound

이 글에서 할 일: 반열린 구간으로 lower bound를 구현하고 존재 여부 검사에 연결합니다. 선수 지식: 정렬된 배열·인덱스·반복문.

반열린 구간으로 첫 위치를 찾습니다

JavaScript 예제: 찾는 값 이상인 첫 위치와 값의 존재 여부를 구합니다. 아래 코드와 실행 결과를 읽고, 이어지는 구간 변화 표로 후보 범위가 줄어드는 과정을 따라가 보세요. 직접 실행하지 않아도 설명을 이해할 수 있습니다.

function lowerBound(values, target) {
  let left = 0;
  let right = values.length; // 후보 구간 [left, right)
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (values[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

function contains(values, target) {
  const index = lowerBound(values, target);
  return index < values.length && values[index] === target;
}

console.log(lowerBound([1, 3, 3, 7], 3));
console.log(contains([1, 3, 3, 7], 5));
console.log(lowerBound([], 3));

실행 결과

1
false
0

[left,right)는 left를 포함하고 right는 포함하지 않는 구간입니다. 시작은 [0,N)이며 N은 읽을 인덱스가 아니라 구간의 끝입니다. 중간값이 target보다 작으면 그 위치까지 답이 아니므로 left = mid + 1로 옮깁니다. 그렇지 않으면 mid가 첫 후보일 수 있으므로 right = mid로 남깁니다.

구간 바깥에 대해 알고 있는 사실을 유지합니다

항상 left 앞의 값은 모두 target보다 작고, right부터 뒤의 값은 모두 target 이상입니다. 아직 판정하지 않은 부분만 [left,right)에 남습니다. 구간 길이는 매번 줄어들며 left와 right가 같아지면 그 경계가 첫 후보 위치입니다.

찾는 값보다 모두 작으면 N을 반환합니다. 따라서 존재 여부는 인덱스가 N보다 작은지 확인한 뒤 실제 값도 비교해야 합니다. lower bound 자체는 값이 없더라도 삽입할 경계를 돌려줍니다.

node --version

node lower-bound.js

구간 규칙과 정렬 비용을 섞지 않습니다

닫힌 구간 [left,right]으로 존재 여부를 찾는 방식도 있습니다. 그 방식의 초기 right=N-1, 반복 left≤right, 제외 시 right=mid-1을 반열린 코드에 부분적으로 섞으면 누락이나 무한 반복이 생깁니다. 한 방식을 끝까지 유지하세요.

정렬된 배열을 한 번 찾는 시간은 O(log N), 추가 공간은 O(1)입니다. 정렬되지 않았다면 정렬 비용도 필요합니다. 비교 정렬 O(N log N) 후 Q번 찾으면 총 O(N log N + Q log N)입니다. 질의가 한 번뿐이면 O(N) 선형 탐색이 더 단순할 수 있습니다.

이 코드는 랜덤 접근이 가능한 배열의 이진 탐색입니다. 노드와 연결로 값을 저장하는 이진 탐색 트리의 삽입·삭제 연산과는 구분합니다. 입력은 오름차순이며 NaN처럼 순서 비교가 성립하지 않는 값은 제외합니다.

직접 확인하고 문제에 적용하기

[2,2,5]에서 target을 1, 2, 4, 9로 바꾸면 lower bound는 각각 얼마일까요?

• 이진 탐색 연습 — 숫자 카드 존재 여부
• 배열 인덱스 조회와 연산 비용

참고 자료

자료 확인일: 2026년 10월 19일.

• C++ 표준 초안 — lower_bound — 비교 조건으로 나뉜 범위에서 첫 경계 반환.