二分探索の境界条件設計

二分探索は、ソート済みのデータ構造から特定の要素を対数時間で検索するための基盤技術である。実装上の最も重要な要素は、探索区間の定義とループ継続条件の整合性を取り持つことにある。区間の表現方法により、実装パターンは大きく二つに分類される。

一つ目は両端を含む閉区間 `[lo, hi]` を採用する手法である。この場合、左端ポインタが右端ポインタと等しい時点でも有効な探索対象が残っている可能性があるため、継続条件は `lo <= hi` と定義される。中央値が目的値よりも大きい場合は `hi` を `mid - 1` に、小さい場合は `lo` を `mid + 1` に更新する。

// 時間計算量: O(log n) / 空間計算量: O(1)
func binarySearchClosed(arr []int, goal int) int {
    lo, hi := 0, len(arr)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == goal {
            return mid
        } else if arr[mid] < goal {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

二つ目は右端を含まない半開区間 `[lo, hi)` を採用する手法である。この定義では `lo == hi` となった時点で探索範囲が空となるため、ループ条件は `lo < hi` で十分である。中央値が目的値より大きい場合、中央要素自体は対象から除外されるが、右端ポインタは `mid` に更新される。

// 時間計算量: O(log n) / 空間計算量: O(1)
func binarySearchHalfOpen(arr []int, goal int) int {
    lo, hi := 0, len(arr)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == goal {
            return mid
        } else if arr[mid] < goal {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return -1
}

挿入位置の特定と下限値探索

配列内に目的値が存在しない場合、ソート順を維持したまま要素を挿入すべきインデックスを特定する必要がある。この問題は、二分探索の変形である「下限値探索（Lower Bound）」として定式化できる。探索ループが終了した時点で、左端ポインタ `lo` が常に有効な挿入候補となる性質を利用する。

func findInsertIndex(arr []int, goal int) int {
    lo, hi := 0, len(arr)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == goal {
            return mid
        }
        if arr[mid] < goal {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return lo
}

対象値の出現範囲の抽出

ソート済み配列内で重複可能な値が出現する最初と最後のインデックスを求める場合、単一の探索では不十分である。左境界と右境界を独立して検索するアプローチが確実である。一致した要素を発見した後も探索を継続させ、それぞれの方向へ境界を押し広げることで、正確な範囲を特定できる。

func locateBoundaries(arr []int, goal int) []int {
    left := searchEdge(arr, goal, true)
    right := searchEdge(arr, goal, false)
    if left == -1 || right == -1 {
        return []int{-1, -1}
    }
    return []int{left, right}
}

func searchEdge(arr []int, goal int, searchLeft bool) int {
    lo, hi := 0, len(arr)-1
    res := -1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == goal {
            res = mid
            if searchLeft {
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        } else if arr[mid] < goal {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }
    return res
}

インプレースな要素のフィルタリング

配列から特定の値を削除し、残りの要素を先頭から詰めて返す処理では、追加のメモリ確保を避けることが求められる。双指针（Two Pointers）テクニックを適用し、読み込み用ポインタと書き込み用ポインタを分離することで、線形時間内でのインプレース更新を実現する。読み込みポインタが目的値を指している場合はスルーし、それ以外の場合のみ書き込みポインタへ要素をコピーしてインクリメントする。

// 時間計算量: O(n) / 空間計算量: O(1)
func filterValue(arr []int, target int) int {
    writeIdx := 0
    for readIdx := 0; readIdx < len(arr); readIdx++ {
        if arr[readIdx] != target {
            arr[writeIdx] = arr[readIdx]
            writeIdx++
        }
    }
    return writeIdx
}

ソート済み配列の平方計算

昇順にソートされた整数配列の各要素を二乗した結果を、再び非減順で並べ替える問題を考える。負数が含まれるため、単純な順方向計算では順序が保てない。しかし、絶対値が最大となる要素は必ず配列の両端に位置する性質を利用できる。両端からポインタを内側へ寄せながら、平方値の大小を比較し、大きい方を結果配列の末尾から順に埋めていく手法が効率的である。

// 時間計算量: O(n) / 空間計算量: O(n)
func computeSortedSquares(arr []int) []int {
    n := len(arr)
    result := make([]int, n)
    left, right := 0, n-1
    pos := n - 1

    for left <= right {
        lSq := arr[left] * arr[left]
        rSq := arr[right] * arr[right]
        if lSq > rSq {
            result[pos] = lSq
            left++
        } else {
            result[pos] = rSq
            right--
        }
        pos--
    }
    return result
}