Leetcode diary: 33. 回転ソート配列で検索

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

link

ステロイドの二分探索!!これはおそらく、変更された二分探索問題を忘れていないかどうかを確認できるように、時々戻ってくる良い質問です.

ソートされた個別の整数の配列と、それらのそれぞれがいくつかのランダムな定数 K インデックスによって回転されるという事実が与えられた場合、ターゲットが存在するインデックスを見つけるか、-1 を返します. Kは与えられていません.
質問は、log N 時間でこれを行う必要があることを指定しています.

log N でなければならないので、二分探索を意味するに違いありません.質問は、回転した配列でバイナリ検索を行う方法です.

二分探索では配列をソートする必要があることを思い出してください.ただし、ソートされた配列をローテーションした場合はそうではありません.したがって、[4,5,6,7,8,9,1,2,3] を持つことができます.配列内の 6 などを見つけるにはどうすればよいでしょうか.

最初に、回転された並べ替えられた配列で二分探索を行う方法を考えた後、スクロールします...
.
.
.
.
.
.
.
.
.
.
.
.
.
答えは、配列内の最小値のインデックスとも呼ばれる変曲インデックスを見つけて、この配列に対して 2 つのバイナリ検索を実行するとどうなるかということです. 0 から始まり、変曲点 -1 で終わるものと、配列の最後までの変曲点を行うことができます.

では、二分探索を変更するにはどうすればよいでしょうか.
これが二分探索の一般式であることを思い出してください.

function binarySearch (nums, target) {
    let start,mid,end;
    start = 0; end = nums.length-1;

    while (start <= end) {
        mid = Math.floor((start+end)/2);
        if(nums[mid] === target) return mid;

        if (mid > target) {
            end = mid-1;
        } else {
            start = mid+1 
        }
    }

}

これ (またはこれのバージョン) を必ず覚えておく必要があります.問題は、変曲点を見つけるためにこれをどのように行うかということです.
二分探索には、次の 2 つの主要部分があります.
1.) ターゲットは何ですか
2.) mid != target の場合、どのように移動しますか
変曲点の数値は何でもよいため、配列の正確なターゲット値はありません.私たちはそれが最小であることだけを知っています.ただし、これが回転ソートされた配列であることもわかっています.これは、すべての要素が小さいものから大きいものへと変化することを意味しますが、ローテーションにより、どこかのインデックスが大きいものから小さいものへと変化します.
したがって、ミッドチェックを次のように変更できます.if(nums[mid-1] > nums[mid]).配列が実際に回転していない場合でも、変曲点を取得できますか?答えはイエスです.技術的には、この特定のバイナリ検索式の優れた点は、回転していない配列の特定のケースでは、開始値が最小値のインデックス (もちろん 0) になることです.

問題は、ターゲットなしでどのように移動するかです.精神的なギャップは、二分探索がソートされた配列に依存していることですが、より技術的には、決定的な方向性の感覚です.私たちは決定的な方向感覚を持っているでしょうか?技術的にはい、これは起こり得ることです
1.) 数値[中間] > 数値[終了]
2.) 数値[中間] < 数値[終了]

nums[mid] > nums[end] は、回転が (nums.length/2) を過ぎたときに発生します.これは、[3,4,5,6,7,8,1 のように、屈曲が後半にあることを意味します. 、2]
半分の長さの回転を過ぎていない場合:
[5,6,7,8,1,2,3,4]
[7,8,1,2,3,4,5,6]

nums[mid] < nums[end] は、回転が行き過ぎていないことを意味するため、左側に移動して最小値を見つけることができます

したがって、変曲点を見つけるためにすべきことは次のとおりです.

    let start, mid, end;
    start = 0; end = nums.length-1;

    while ( start <= end ) { //find inflection
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid } 
        if(nums[mid-1] > nums[mid] ) { start = mid; break; }

        if(nums[mid] > nums[end]) {
            start = mid+1; //find later half
        }
        else {
            end = mid-1; //find in first half
        }
    }

    const inflection = start;

インタビューでは、おそらく [7,1] のような単純なケースを実行して、語形変化として開始できることを証明したいと思うでしょう.

屈折が完了したので、これで文字通り作業の 95% が完了しました.残りは、2 つのバイナリ検索を実行することです.1 つは屈折 1 で終わり、もう 1 つは屈折で始まります.それだけです.以下の完全なコード:

var search = function(nums, target) {
    let start, mid, end;
    start = 0; end = nums.length-1;

    while ( start <= end ) { //find inflection
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid } 
        if(nums[mid-1] > nums[mid] ) { start = mid; break; }

        if(nums[mid] > nums[end]) {
            start = mid+1;
        }
        else {
            end = mid-1;
        }
    }

    const inflection = start;

    start = 0;
    end = inflection - 1;
    while ( start <= end ) { //<= to not check start after while ends
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid }

        if(nums[mid] > target) {
            end = mid-1;
        }
        else {
            start = mid+1;
        }
    }

    start = inflection;
    end = nums.length - 1;
    while ( start <= end ) { //<= to not check start after while ends
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid }

        if(nums[mid] > target) {
            end = mid-1;
        }
        else {
            start = mid+1;
        }
    }

    return -1;

};

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