二分探索 ||パイソン ||データ構造とアルゴリズム

二分探索

二分探索 は、探索空間を繰り返し半分に分割するアルゴリズムです。この検索手法は分割統治戦略に従います。検索空間は反復ごとに常に半分に減少します。その結果、時間計算量は O(log(n)) になります。ここで、n は要素の数です。

条件: 配列はソートされる必要がありますが、単調増加または単調減少を見つける必要がある単調関数にも適用できます。

対数時間で検索空間を絞り込む必要がある場合に機能します。

左右の 2 つのポインターを使用します。左右の平均をとって中央の要素を見つけます。

次に、条件に基づいて左右のポインターをどこに移動するかを確認します。

問題を解決するには主に 3 つの手順が必要です:

1. 前処理: 入力がソートされていない場合はソートします。
2. 二分探索: 2 つのポインターを使用して検索空間を分割する中央を見つけ、それに応じて正しい半分を選択します。
3. 後処理: 出力を決定します。

二分探索アルゴリズムの利点 - 二分探索は、各要素を 1 つずつチェックするのではなく、毎回配列を半分に分割するため、大きなデータの線形探索よりも高速です。これにより、作業がより迅速かつ効率的に行われます。

制限事項: 二分検索はソートされた配列でのみ機能するため、ソートに余分な時間がかかるため、ソートされていない小さな配列では効率的ではありません。また、小規模なメモリ内検索では線形検索ほど機能しません。

アプリケーション: これは、O(log(n)) 時間計算量でソートされた配列内の要素を検索するために使用されます。また、配列内の最小または最大の要素を見つけるために使用することもできます。

基本的な二分探索コード -

コード

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

33.回転ソート配列で検索
可能な回転後の配列 nums と整数ターゲットを指定すると、ターゲットが nums 内にある場合はターゲットのインデックスを返し、nums 内にない場合は -1 を返します。
実行時の複雑度が O(log n) のアルゴリズムを作成する必要があります。
例 1:
入力: 数値 = [4,5,6,7,0,1,2]、ターゲット = 0
出力: 4

例 2:
入力: 数値 = [4,5,6,7,0,1,2]、ターゲット = 3
出力: -1

例 3:
入力: 数値 = [1]、ターゲット = 0
出力: -1

コード

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

1. 左右の 2 つのポインターを使用し、重なるまで繰り返します。
2. 中間要素を見つけます。
3. 配列はソートされていますが回転されているため、左または右の要素を中央の要素と単純に比較することはできません。
4. まず、中央のポインタと左または右のポインタを比較して、左右どちらの部分がソートされるかを決定します。
5. この結論に基づいて、ポインタを適宜調整します。

時間計算量 - O(log(n)) (探索空間は各反復で半分に分割されるため)。
空間の複雑さ - O(1)

単調増加

162.ピーク要素の検索

ピーク要素は、隣接する要素よりも厳密に大きい要素です。
0 から始まるインデックスの整数配列 nums を指定すると、ピーク要素を見つけて、そのインデックスを返します。配列に複数のピークが含まれる場合は、いずれかのピークのインデックスを返します。
nums[-1] = nums[n] = -∞ と想像できるかもしれません。言い換えれば、要素は常に、配列の外側にある隣接要素よりも厳密に大きいと見なされます。
O(log n) 時間で実行されるアルゴリズムを作成する必要があります。

例 1:
入力: nums = [1,2,3,1]
出力: 2
説明: 3 はピーク要素であり、関数はインデックス番号 2 を返す必要があります。
例 2:
入力: nums = [1,2,1,3,5,6,4]
出力: 5
説明: 関数は、ピーク要素が 2 であるインデックス番号 1、またはピーク要素が 6 であるインデックス番号 5 を返すことができます。

コード

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. このタイプの問題では、中音域の左または右の要素を比較してピークをチェックする必要があります。
2. これは、グラフが上昇傾向にあるのか下降傾向にあるのかを判断するのに役立ちます。
3. 最大値を見つけるには、上り坂を検索し、適切な部分空間を探索します。
4. 最小値を見つけるには、左の部分空間を検索します

時間計算量 - O(log(n)) (探索空間は各反復で半分に分割されるため)。
空間の複雑さ - O(1)

以上が二分探索 ||パイソン ||データ構造とアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。