クラウド 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 に更新すると、要素数が二つの場合にループが終了しなくなることがあります。

空配列のための特別な分岐は不要です。ループは一度も実行されず、そのままゼロを返します。空配列に対応するために count - 1 を持ち込むと、負の添字や閉区間での終了条件という問題が再び生じます。

線形探索を基準に小さな入力をすべて検証する

参照実装は単純であるべきで、別の二分探索を書いてはいけません。同じファイルに次のコードを追記します。長さがゼロから六、要素の値がゼロから三のすべての非減少配列を列挙し、値域の内側と外側の探索値を検証します。

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 を実行し、終了コードがゼロなら、すべての検証条件を満たしています。失敗した場合、プロセスはゼロ以外の終了ステータスで終了します。このスクリプトでは、最適化ビルドで取り除かれる可能性がある通常の assert は使いません。安全性チェックを無効にするコンパイルオプションも使わないでください。

探索結果を業務ロジックのインターフェースにつなぐ

要素の存在を調べる場合は、まず下限を求めます。その位置が配列の要素数より小さく、かつ対応する値が探索値と等しい場合に限り、見つかったと判定します。重複する値をまとめて取得するには、lower..<upper のスライスを使います。探索値が存在しなければ、自然に空のスライスになります。

ソートと比較の基準をそろえる

配列にレコードを格納し、タイムスタンプを基準にソートするなら、探索でも同じタイムスタンプの意味に基づいて比較しなければなりません。時刻の昇順にソートしておきながら、探索では表示用の文字列を比較していては、アルゴリズム自体が正しくても役に立ちません。

タイムスタンプが同じレコードについて到着順を保ちたい場合は、上限の位置に挿入できます。業務上の優先順位もあるなら、挿入位置にソート規則の代わりをさせるのではなく、完全なソートキーを先に定義してください。降順の配列には、ここで使った比較条件をそのまま適用できません。

探索中は配列を変更しないことも重要です。非同期処理で位置を取得した後に配列が変更されると、その位置はすでに無効になっている可能性があります。探索と挿入は同じ分離ドメイン内で完結させるか、同一の不変スナップショットを対象に処理してください。

失敗した入力を回帰テストに残す

プロジェクトのテストに組み込む際は、固定した業務ケース、小さな配列の全列挙、実レコードのソート契約という三層の検証を残してください。戻り値が有効な範囲内にあるかだけでは不十分です。範囲内でも、正しい位置から一つずれている可能性があります。

• 空配列、単一要素、すべて同じ値、探索値が両端の外側にある場合を網羅する。
• 下限より左の値がすべて探索値未満で、上限以降の値がすべて探索値より大きいことを確認する。
• 重複区間の長さが、線形走査で数えた出現回数と一致することを確認する。
• 失敗した配列、探索値、期待する位置を固定テストケースとして保存する。
• 実際に使用するツールチェーンとコンパイル設定で再実行する。

小さな入力の全列挙は、あらゆる整数入力で正しいことの証明にはなりません。それでも、重複値の扱いと区間を縮める経路を体系的に検証できます。後でジェネリックな比較器に置き換える場合も、線形探索による参照実装と分割条件の検証は残し、変わらないインターフェース契約の上で最適化を進めてください。

よくある質問