Leetcode diary: 153. Rotated Sorted Array の最小値を見つける [二分探索]

これは新しいシリーズで、リートコードの質問に苦戦している様子を記録しています.たとえ少数の聴衆であっても、継続するモチベーションを与えてくれることを願っています.

link

この質問は素晴らしかったです.私は修正二分探索を練習しなければなりませんでした.完了し、他の人が一般的にどのようにアプローチしたかを確認した後、私はより良いものを手に入れました!コードは議論中のものと同じですが、私の説明はより包括的です.

問題は、ローテーションされた並べ替えられた配列が与えられた場合に、O(log n) の効率で最小数を見つけることです.
回転された配列は、すべてがシフトされたインデックスの数です.たとえば、この [1,2,3,4,5,6,7,8] の場合:
[8,1,2,3,4,5,6,7]
[7,8,1,2,3,4,5,6]
[6,7,8,1,2,3,4,5]
これらはすべて配列で、それぞれ前のインデックスの 1 つだけ右にシフトされます.

考えられるケースに入る前に、最初に mid 式が次のようになっていることを確認しましょう. Math.floor((left+right)/2);
Math.ceil もやっている人がいると思いますが、二分探索について学んでいるときに最初に見たバージョンの前者を選んだだけです.

また、別の規則である nums[left] も返します.

この問題を理解したところで、考えられるシナリオを見てみましょう.
1.) 数値[中央] > 数値[右]:
[3,4,5,6,7,8,1,2]
[2,3,4,5,6,7,8,1]
上記の2つはその例です.

この場合、正しいものを探すことは論理的に理にかなっています.これは、中間値が正しい値よりも大きい場合、配列が中間点を超えて回転したことを意味するためです.それ以外の場合は、元の配列のように mid < right を取得する必要があります.したがって、最小値は中央インデックスの右側のどこかにあります.
これは例からも明らかですが、完全を期すために説明しただけで、例による証明は通常 100% 機能しません.

この場合、私たちがすべきことは次のとおりです.
左 = 中央 + 1.

ここでの +1 は非常に重要です.これは、左または右の値に答えが含まれている場合にエッジ ケースを処理する必要があるためです.ただし、この if ステートメント内では、right could = min のみが可能です.
つまり

左 = 0、右 = 1、つまり中央 = 0
nums[mid] > nums[right] を満たします.
左===右、これを終了して答えを返すことができます.

2.) 数値[中央] <= 数値[右]:
[6,7,8,9,1,2,3,4,5]//答え === 半ば
[6,7,8,1,2,3,4,5]//答え === 半ば
[7,8,9,1,2,3,4,5,6]//答え === 真ん中の左
[7,8,1,2,3,4,5,6]//答え === 真ん中の左

左を見ると、これは最初の mid が正確に答えである場合も処理するため、次のようにする必要があります.
右=中;そのため、答えがプロセスで除外されることはありません.
今それを見てください
[1,2] 反対はすでに前者で処理されているため
左=0、中=0、右=1
nums[mid] <= nums[right] を満たす
right=mid なので、 left === mid で終了し、答えを返します.

ここで、上記の例を試して、2 つの条件がどのように回転し、[7,1] または [1,2] エンドゲームに向かって進むかを確認する必要があります.以下の完全なコード:

var findMin = function(nums) {
    let left, right, mid;
    left  = 0;
    right = nums.length-1;

    while (left < right) {
        mid = Math.floor((left+right)/2);
        if(nums[mid] > nums[right]) {
            left = mid+1
        } else {
            right = mid
        }
    }

    return nums[left];
}

私の最初の解決策は以下のとおりです.コード自体はより系統的で、一種の自己文書化されていますが、はるかに複雑であり、明示的に処理する必要がある奇妙なエッジケースがあります.インタビュアーが上記の方法を好むことは承知していますが、コードが完全に完成していなくても、以下の方法で多くのポイントを獲得できます.

var findMin = function(nums) {
    let mid, start, end, midI, prevI, nextI
    start = 0;
    end = nums.length-1;


    while (start < end) {
        midI = Math.floor((start+end)/2);
        prevI = midI-1 > -1 ? midI-1: nums.length-1;
        nextI = midI+1 === nums.length ? 0 : midI+1;

        mid = nums[midI]

        if(nums[prevI] > mid && mid < nums[nextI]) { //7,0,1
            return mid;
        }

        if(nums[start] > mid && mid < nums[end]) {
            // go toward the bigger end
            if(nums[start] > nums[end]) {
                end = midI-1; 
            } else {
                start = midI+1;
            }
        }

        if(nums[start] <= mid && mid > nums[end]) {
            // go toward the smaller end
            if(nums[start] > nums[end]) {
                start = midI+1;
            } else {
                end = midI-1; 
            }

        }

        if(nums[start] < mid && mid < nums[end]) {
            // go toward start
            end = midI-1;
        }
    }

    return nums[start]
};

nums[start] > mid && mid > nums[end] は、配列が最小から最大の順にソートされるため、使用できないことに注意してください.

2 つのソリューションの主な概念上の違いは、一方が右に見えることです.
これは、発達させなければならない一種の直感だと思います.これまでのところ、考えられるすべてのケースを詳細に調べています:(

これを読んだ後、あなたの心に何か教えてください、ありがとう!