41. Search Insert Position

読了目安約1分

Binary Search / LeetCode 35 (Easy) — ソート済み配列に target を挿入すべき位置を二分探索で求める。

この章の目次

問題

LeetCode 35. Search Insert Position（Easy / カテゴリ: Binary Search）

昇順にソートされた相異なる整数の配列 nums と整数 target が与えられます。 target が配列にあればその位置を、なければソート順を保ったまま挿入できる位置を返します。 O(log n) で解くことが求められています。

考え方

ヒント 1

「target 以上の値が初めて現れる位置」を探すと考えます。 target が存在する場合と存在しない場合を、同じコードで扱えます。

ヒント 2

探索範囲を low = 0、high = nums.count の半開区間で持ちます。 nums[mid] < target なら low = mid + 1、そうでなければ high = mid と縮めます。 low == high になった位置が答えです。

Swift 実装のポイント

high は nums.count - 1 ではなく nums.count から始めます。挿入位置は配列の末尾になりえます。
ループ条件は low < high です。low <= high にすると、high = mid が範囲を縮めず無限ループします。
この「条件を満たす最小の位置」を返す形は lower bound と呼ばれる二分探索の定型です。

模範解答

Swift
class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var low = 0
        var high = nums.count
        while low < high {
            let mid = (low + high) / 2
            if nums[mid] < target {
                low = mid + 1
            } else {
                high = mid
            }
        }
        return low
    }
}

計算量: O(log n)。