アルゴリズム_二分探索

Algorithem_BinarySearch#

BinarySearch#

与えられた整数の配列 nums が昇順にソートされており、整数 target が与えられたとき、nums の中で target を検索する関数を書いてください。target が存在する場合、そのインデックスを返します。そうでない場合は -1 を返します。

O (log n) の実行時間のアルゴリズムを記述する必要があります。

制約:
nums のすべての整数はユニークです。
nums は昇順にソートされています。

解法#

最初の考えは、毎回配列の中央 middleIndex から検索を開始し、配列の中央の数字と target の大きさを比較し、target が大きければ middleIndex から配列の末尾までの配列を切り取って新しい配列を生成し、target が小さければ 0 から middleIndex までの新しい配列を生成し、等しい場合は直接インデックスを返すというものでした。そして、新しく生成された配列で再度比較し、再帰的に自身を呼び出します。しかし、この方法では、毎回再帰の開始位置を記録する必要があり、最後に見つけたときに、見つけたインデックスに開始位置を加算または減算する必要があります。

公式アルゴリズム：

配列の中央から検索を開始し、左（left）と右（right）を宣言して、検索する配列の開始位置と終了位置を表します。
while を使用し、left <= right が条件となり、次に繰り返します。
- middleIndex = left + (right - left) / 2
- target < middleNum の場合、target は left から middle-1 の間にあることを示します；
- target > middleNum の場合、target は middle + 1 から right の間にあることを示します；
- target == middleNum の場合、直接 middleIndex を返します。

境界値テスト：

要素が 1 つの場合、left=0、right=0、left=right、middleIndex=0、nums [middleIndex] が target と等しいかどうかを判断します。
要素が 2 つの場合、left=0、right=1、left<right、middleIndex=0、nums [middleIndex] と target の大きさを判断します。
- もし target <nums [middleIndex] なら、right = middleIndex-1=-1、left > right となり、ループ条件を満たさないため、配列にこの要素は存在しないことを示し、-1 を返します。
- もし target > nums [middleIndex] なら、left = middleIndex+1=1、left = right となり、次の繰り返しを続けます。left=1、right=1、middleIndex=1、nums [middleIndex] と target の大きさを判断します。
- もし target = nums [middleIndex] なら、middleIndex を返します。

コードは以下の通りです：


class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        let count = nums.count
        
        var left = 0
        var right = count - 1
        var findIndex = 0
        
        while (left <= right) {
            findIndex = left + (right - left) / 2
            
            let num = nums[findIndex]
            if target < num {
                right = findIndex - 1
            }
            else if target > num {
                left = findIndex + 1
            }
            else {
                return findIndex
            }
        }
        return -1
    }
}

FirstBadVersion#

あなたはプロダクトマネージャーで、新しい製品の開発をリードするチームを率いています。残念ながら、あなたの製品の最新バージョンは品質チェックに失敗しました。すべてのバージョンは前のバージョンに基づいて開発されるため、悪いバージョンの後のすべてのバージョンも悪いです。

n バージョン [1, 2, ..., n] があり、最初の悪いバージョンを見つけたいとします。これにより、すべての後続のバージョンが悪くなります。

API bool isBadVersion (version) が与えられ、version が悪いかどうかを返します。最初の悪いバージョンを見つける関数を実装してください。API への呼び出しの回数を最小限に抑える必要があります。

解法#

最初の考えは、BinarySearch に似ていて、まず中間値から始め、中間が BadVersion であれば前に進み、中間が BadVersion でなければ後ろに進むというものでした。しかし、終了条件はずっと理解できませんでした。

公式アルゴリズム：

配列の中央から検索を開始し、左（left）と右（right）を宣言して、検索する配列の開始位置と終了位置を表します。
while を使用し、left < right が条件となり、次に繰り返します。
- middleIndex = left + (right - left) / 2
- middleIndex が BadVersion の場合、最初の BadVersion は left から middleIndex の間にあることを示します。ここで注意が必要なのは、現在の middleIndex が最初の BadVersion である可能性があるため、取得する際には middleIndex を含める必要があります。
- middleIndex が BadVersion でない場合、最初の BadVersion は middleIndex + 1 から right の間にあることを示します。

テスト：


Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = Good, B = Bad
 |       |       |
left    mid    right

Scenario #1 詳細：

left=1, right=9; left <right; middle = 5, isBadVersion (5) = false、つまり 5 は良いので、悪いバージョンは 6~9 の間にあります；left を 6 に設定します。
left=6, right=9; left <right; middle = 7, isBadVersion (7) = true、つまり 7 は悪いので、悪いバージョンは 6~7 の間にあります；right を 7 に設定します。
left=6, right=7; left <right; middle = 6, isBadVersion (6) = false、つまり 6 は良いので、悪いバージョンは 7~7 の間にあります；left を 7 に設定します。
left=7, right=7; left = right; ループ条件を満たさず、最終的に left=7、7 が最初の悪いバージョンです；


Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = Good, B = Bad
 |       |       |
left    mid    right

Scenario #2 詳細：

left=1, right=9; left <right; middle = 5, isBadVersion (5) = true、つまり 5 は悪いので、悪いバージョンは left~5 の間にあります；right を 5 に設定します。
left=1, right=5; left <right; middle = 3, isBadVersion (3) = false、つまり 3 は良いので、悪いバージョンは 4~right の間にあります；left を 4 に設定します。
left=4, right=5; left <right; middle = 4, isBadVersion (4) = true、つまり 4 は悪いので、悪いバージョンは left~4 の間にあります；right を 4 に設定します。
left=4, right=4; left = right; ループ条件を満たさず、最終的に left=4、4 が最初の悪いバージョンです；

コードは以下の通りです：

/**
 * The knows API is defined in the parent class VersionControl.
 *     func isBadVersion(_ version: Int) -> Bool{}
 */

class Solution : VersionControl {
    func firstBadVersion(_ n: Int) -> Int {
        var left = 1
        var right = n
        
        while left < right {
            let middle = left + (right - left) / 2
            let isBad = isBadVersion(middle) 
            if isBad {
                right = middle
            }
            else {
                left = middle + 1
            }
        }
        
        return left
    }
}

Search Insert Position#

与えられた異なる整数のソートされた配列とターゲット値があり、ターゲットが見つかった場合はインデックスを返します。見つからない場合は、順序で挿入されるべきインデックスを返します。

O (log n) の実行時間のアルゴリズムを記述する必要があります。

解法#

この解法は BinarySearch と論理が同じで、唯一の違いは、BinarySearch では見つからない場合に -1 を返しますが、この検索では見つからない場合は最終的に left の位置を返します。

コードは以下の通りです：


class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        
        var left = 0
        var right = nums.count - 1
        var middle = 0
        while left <= right {
            middle = left + (right - left) / 2
            
            let middleNum = nums[middle]
            if target < middleNum {
                // means target in left..<middle
                right = middle - 1
            }
            else if target > middleNum {
                // means targets in middle..<right
                left = middle + 1
            }
            else {
                // equal return middleNum
                return middle
            }
        }
        
        return left
    }
}