클라우드 Mac에서 iOS 이진 탐색의 삽입 경계 검증

Windows에서 목록 로직을 구현한 뒤 Swift 코드를 클라우드 Mac으로 옮겨 검증할 때, 가장 놓치기 쉬운 부분은 ‘원소를 찾을 수 있는가’가 아니라 ‘중복값을 어디에 삽입해야 하는가’입니다. 채팅 타임라인, 구간별 눈금, 정렬된 레코드의 인덱스는 모두 이진 탐색에 의존할 수 있습니다. 위치가 한 칸만 어긋나도 일반적인 테스트는 통과하면서 경계 입력에서는 레코드가 누락될 수 있습니다. 여기서는 시뮬레이터를 실행하거나 네트워크 데이터에 의존하지 않고, 독립 실행 스크립트로 인터페이스 계약을 검증합니다.

두 삽입 경계부터 정의하기

입력은 오름차순으로 정렬된 정수 배열이라고 가정합니다. 하한은 목표값보다 크거나 같은 첫 번째 원소의 위치를, 상한은 목표값보다 엄격히 큰 첫 번째 원소의 위치를 반환합니다. 상한에서 하한을 빼면 목표값의 등장 횟수가 됩니다.

예를 들어 배열 [1, 2, 2, 4]에서 2를 찾으면 하한은 1, 상한은 3입니다. 5를 찾으면 둘 다 4를 반환합니다. 이는 탐색 실패가 아니라 배열 끝에 삽입할 위치를 뜻합니다.

반환 위치는 배열 길이와 같을 수 있지만, 원소를 읽는 인덱스는 그럴 수 없습니다. 먼저 범위를 확인한 뒤 원소에 접근해야 합니다. 끝 삽입 위치를 마지막 원소의 인덱스로 대신해서는 안 됩니다.

여기서는 -1 센티널을 사용하지 않으며, 함수가 입력을 자동으로 정렬하지도 않습니다. 자동 정렬은 호출 측에서 정렬되지 않은 데이터를 넘긴 문제를 숨기고, 레코드 사이의 기존 순서 관계까지 깨뜨릴 수 있습니다.

반열린 구간으로 탐색 구현하기

클라우드 Mac에 로그인한 뒤 자신의 작업 디렉터리에 BoundsCheck.swift를 만듭니다. 먼저 xcrun --find swift를 실행해 툴체인을 사용할 수 있는지 확인하고, 다음 구현을 작성합니다. 탐색 구간은 항상 [lo, hi)이며, 오른쪽 경계의 초깃값은 배열 길이입니다.

func lowerBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] < target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

func upperBound(_ values: [Int], _ target: Int) -> Int {
    var lo = 0
    var hi = values.count
    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if values[mid] <= target {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

두 함수는 비교 조건만 다르지만, 이 차이가 중복값을 어느 쪽에 포함할지 결정합니다. 중간 위치는 양 끝값을 직접 더하지 않도록 lo + (hi - lo) / 2로 계산합니다. 반복할 때마다 구간이 반드시 줄어들어야 합니다. 왼쪽 경계를 mid로 갱신하면 원소가 두 개인 입력에서 반복이 끝나지 않을 수 있습니다.

빈 배열에는 별도 분기가 필요 없습니다. 반복문을 실행하지 않고 바로 0을 반환합니다. 빈 배열을 처리하려고 count - 1을 도입하지 마세요. 음수 인덱스와 닫힌 구간의 종료 조건 문제가 다시 생깁니다.

선형 기준 구현으로 모든 작은 입력 검증하기

기준 구현은 또 다른 이진 탐색이 아니라 단순한 구현이어야 합니다. 다음 코드를 같은 파일에 덧붙입니다. 길이가 0부터 6까지이고 원소의 값이 0부터 3까지인 모든 비내림차순 배열을 생성한 뒤, 해당 범위 안팎의 목표값을 검사합니다.

func verify(_ values: [Int]) {
    for target in -1...4 {
        let lower = lowerBound(values, target)
        let upper = upperBound(values, target)
        let expectedLower =
            values.firstIndex(where: { $0 >= target }) ?? values.count
        let expectedUpper =
            values.firstIndex(where: { $0 > target }) ?? values.count

        precondition(lower == expectedLower)
        precondition(upper == expectedUpper)
        precondition(lower <= upper)
        precondition(values[..<lower].allSatisfy { $0 < target })
        precondition(values[lower...].allSatisfy { $0 >= target })
        precondition(values[..<upper].allSatisfy { $0 <= target })
        precondition(values[upper...].allSatisfy { $0 > target })
    }
}

func enumerate(_ prefix: [Int], remaining: Int, minimum: Int) {
    if remaining == 0 {
        verify(prefix)
        return
    }
    for value in minimum...3 {
        enumerate(prefix + [value],
                  remaining: remaining - 1,
                  minimum: value)
    }
}

for length in 0...6 {
    enumerate([], remaining: length, minimum: 0)
}
verify([Int.min, 0, Int.max])
precondition(lowerBound([Int.min, 0, Int.max], Int.min) == 0)
precondition(upperBound([Int.min, 0, Int.max], Int.max) == 3)

xcrun swift BoundsCheck.swift를 실행합니다. 종료 코드가 0이면 모든 검증을 통과한 것이며, 실패하면 프로세스가 0이 아닌 상태로 종료됩니다. 이 스크립트는 최적화 빌드에서 제거될 수 있는 일반 assert를 사용하지 않습니다. 안전성 검사를 비활성화하는 컴파일 옵션도 사용하지 마세요.

검증한 계약을 애플리케이션 인터페이스에 적용하기

원소가 존재하는지 확인할 때는 먼저 하한을 구합니다. 해당 위치가 배열 길이보다 작고 그 위치의 값이 목표값과 같을 때만 일치한 것으로 판단합니다. 중복값 전체를 가져오려면 lower..<upper 슬라이스를 사용합니다. 목표값이 없으면 자연스럽게 빈 슬라이스가 됩니다.

정렬 기준과 비교 기준 일치시키기

배열에 레코드를 저장하고 타임스탬프를 기준으로 정렬한다면, 탐색에서도 동일한 타임스탬프 의미 체계를 사용해야 합니다. 정렬은 시간 오름차순으로 해 놓고 탐색에서는 화면에 표시할 문자열을 비교한다면, 알고리즘 자체가 정확해도 소용이 없습니다.

타임스탬프가 같은 레코드의 도착 순서를 유지해야 한다면 상한 위치에 삽입할 수 있습니다. 업무상 우선순위까지 있다면 삽입 위치로 정렬 규칙을 대신하려 하지 말고, 먼저 완전한 정렬 키를 정의해야 합니다. 내림차순 배열에는 여기서 사용한 비교 조건을 그대로 적용할 수 없습니다.

탐색 중에는 배열도 변경되지 않아야 합니다. 비동기로 위치를 얻은 뒤 배열을 수정하면 이전 위치는 이미 유효하지 않을 수 있습니다. 같은 격리 영역 안에서 탐색과 삽입을 수행하거나, 동일한 불변 스냅샷을 대상으로 작업해야 합니다.

실패 입력을 회귀 테스트 목록으로 남기기

프로젝트 테스트에 통합할 때는 고정된 업무 사례, 작은 배열의 전수 검사, 실제 레코드의 정렬 계약이라는 세 단계 검증을 유지합니다. 반환 위치가 유효한 범위 안에 있는지만 확인해서는 안 됩니다. 범위가 유효해도 위치는 한 칸 어긋날 수 있습니다.

• 빈 배열, 원소가 하나인 배열, 모든 값이 같은 배열, 양 끝 범위를 벗어나는 목표값을 검사합니다.
• 하한 왼쪽의 모든 값이 목표값보다 작고, 상한 위치부터 오른쪽의 모든 값이 목표값보다 큰지 확인합니다.
• 중복 구간의 길이가 선형 순회로 센 개수와 같은지 확인합니다.
• 실패한 배열, 목표값, 예상 위치를 고정 테스트 사례로 저장합니다.
• 실제로 사용하는 툴체인과 컴파일 설정에서 다시 실행합니다.

작은 입력을 전수 검사한다고 해서 모든 정수 입력에 대한 정확성이 증명되는 것은 아닙니다. 하지만 중복값 처리와 탐색 구간이 줄어드는 경로를 체계적으로 검사할 수 있습니다. 나중에 제네릭 비교자를 사용하는 구현으로 바꾸더라도 선형 기준 구현과 구간 분할 검증은 유지해야 합니다. 그래야 최적화 과정에서도 동일한 인터페이스 계약을 지킬 수 있습니다.

자주 묻는 질문