위키득계정 ↗
기술

이진 탐색의 경계 조건

이진 탐색의 경계 조건기술
전제
정렬 또는 단조 조건
구간 표현
양 끝 포함 여부를 일관되게 정의
중복값
왼쪽 경계와 오른쪽 경계 구분
검증 입력
빈 범위와 양 끝 및 같은 값
이진 탐색은 정렬된 범위나 단조롭게 바뀌는 조건에서 후보 구간을 절반씩 줄여 답의 위치를 찾는 방법이다. 중복값의 처리와 구간 경계의 정의를 먼저 정해야 올바른 종료 조건을 만들 수 있다.

무엇을 찾는지 먼저 정하기

값 하나가 존재하는지, 같은 값들 가운데 처음 위치가 어디인지, 특정 값보다 큰 첫 위치가 어디인지는 다른 문제다. 중간값이 목표와 같다고 곧바로 종료하면 첫 위치를 찾는 요구에는 맞지 않을 수 있다. 탐색 전에 답의 의미를 문장으로 정한다. 구간을 줄이는 규칙은 그 의미를 계속 보존해야 한다.

포함하는 끝과 제외하는 끝

구간을 왼쪽 끝은 포함하고 오른쪽 끝은 제외하는 방식으로 표현하면 두 끝이 같은 경우를 빈 범위로 해석할 수 있다. 양 끝을 모두 포함하는 방식도 가능하지만 갱신과 종료 조건을 그 정의에 맞춰야 한다. 두 표현의 식을 섞으면 마지막 후보를 건너뛰거나 같은 구간을 반복하기 쉽다. 매 단계 남은 후보가 실제로 줄어드는지 확인한다.

중복값의 두 경계

정렬된 자료 2, 4, 4, 4, 9에서 4를 넣을 왼쪽 경계는 0부터 센 위치 1이고 오른쪽 경계는 4다. 왼쪽 경계는 4보다 작은 값들의 뒤이며 오른쪽 경계는 4 이하 값들의 뒤다. 이 차이를 이용하면 같은 값의 범위도 구할 수 있다. 다만 삽입 위치가 나왔다는 사실만으로 그 값이 실제로 존재한다고 판단하지 않는다.

존재하지 않는 값

모든 값보다 작은 값을 찾으면 경계가 맨 앞일 수 있고 모든 값보다 큰 값을 찾으면 맨 뒤의 제외 경계일 수 있다. 결과를 배열 원소처럼 바로 읽으면 범위를 벗어날 수 있으므로 위치의 유효성을 먼저 확인한다. 빈 배열과 원소 하나의 배열도 같은 규칙으로 동작하는지 검사하면 경계 오류를 좁히기 쉽다.

탐색 뒤의 작업 비용

정렬된 배열에서 위치를 찾는 비용과 그 자리에 원소를 넣는 비용은 다르다. 위치 탐색이 빠르더라도 삽입을 위해 많은 원소를 이동해야 할 수 있다. 반복 삽입이 주된 작업이라면 전체 비용을 따로 평가한다. 이진 탐색을 사용했다는 사실만으로 이후의 모든 연산이 로그 시간이라고 말할 수는 없다.

관련 문서

이진 탐색 / 알고리즘 / 성능 비교 실험 설계