[leetcode] 問題解答と解説。35. Search Insert Position

森田賢二のleetCode

年末まで毎日leetcodeと向き合います。
今日のLeatCodeはこちら。

Search Insert Position ルール

• numsはsort済みの配列
• numsという数値の配列
• targetとして数値
  を受け取る関数は
  numsの中にもしtargetがあればそのインデックスを
  なければtargetがinstertするべきインデックスを返す
• O(log n)で実行する

というもの

問題

Search Insert Position [easy]

Search Insert Position 解答 一例

見本

    let lo = 0, hi = nums.length; // 最後にinsertする必要もあるため
    while(lo < hi) {
        let mid = lo + Math.floor((hi-lo)/2); // 要素が偶数で真ん中の時2つあるが、その場合lowを取る。 lower mid。
        if (target > nums[mid]) {
            lo = mid + 1 // コンディションが100%確証している時 + 1する。この場合、midは評価したので+1で進める
        } else {
            hi = mid
        }
    }
    return lo;

binarrySearch。また再勉強しました。
((hi-lo) / 2)のところとかブレイクポイント張って確認。

説明によると、midの中央のindexを取るには、
偶数の要素数の時に、低い方を取るか高い方を取るかある
例えば、

let a = [1, 3, 4, 5, 6, 7 , 19, 24]

のような場合、真ん中のインデックスは3 or 4
その際の式は

let a = [1, 3, 4, 5, 6, 7 , 19, 24]

let lo = 0
let hi = a.length -1

let mid = lo + Math.floor((hi - lo + 1) / 2) // 高い方をとる　the upper mid
mid
4
let lo = 0
let hi = a.length -1

let mid = lo + Math.floor((hi - lo) / 2) // 低い方をとる　the lower mid
mid
3

カテゴリー leetCode