[Go/LeetCode] 35. Search Insert Position

概要

↓の解法メモです。
https://leetcode.com/problems/search-insert-position/description/

問題概要

ソートされた配列と追加したい要素が渡されるので、

• 追加したい要素がすでに配列にあるなら、そのインデックス
• 追加したい要素が配列にないなら、追加すべき場所を示すインデックス
  を返します。「追加すべき場所」は、要素を追加してソート順に整列した場合のインデックスを指します。
  たとえば [1,3,5,6] に対して 4 が渡された場合 2 を返します。

追記として、問題文には

You must write an algorithm with O(log n) runtime complexity.
とあるので、計算量が $O(logN)$ になるように書いていきます。

解法

二分探索を使用します。
配列の中間値と追加要素を比較し、

• 中間値 < 追加要素　　なら中間値より右の値を対象に再探査
• 中間値 > 追加要素　　なら中間値より左の値を対象に再探査
• 中間値 = 追加要素　　ならその値を返す
  を繰り返していきます。

注意点として、必ずしも配列内に追加要素が見つかるとは限りません。そのため、探査の対象要素が1つ以下になったら探査を打ち切り、最後に参照した中間値のインデックスを参照して挿入すべき位置を返します。
ループの終わりに暫定解を保存しておき、終了条件に達したら自動的に保存していた暫定解を返すかしこい方法だと思います（Solution から参考にしました）。

func searchInsert(nums []int, target int) int {
    var result int
    for l, r := 0, len(nums)-1; l <= r; {
        m := (l+r)/2
        switch {
            case nums[m] < target:
                result = m+1
                l = m+1
            case nums[m] > target:
                result = m
                r = m-1
            default:
                return m
        }
    }
    return result
}