ホームページ バックエンド開発 Python チュートリアル 二分探索 ||パイソン ||データ構造とアルゴリズム

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

Dec 16, 2024 pm 05:24 PM

Binary Search || Python || Data Structures and Algorithms

二分探索

二分探索 は、探索空間を繰り返し半分に分割するアルゴリズムです。この検索手法は分割統治戦略に従います。検索空間は反復ごとに常に半分に減少します。その結果、時間計算量は 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

LinuxターミナルでPythonバージョンを表示するときに発生する権限の問題を解決する方法は? LinuxターミナルでPythonバージョンを表示するときに発生する権限の問題を解決する方法は? Apr 01, 2025 pm 05:09 PM

LinuxターミナルでPythonバージョンを表示する際の許可の問題の解決策PythonターミナルでPythonバージョンを表示しようとするとき、Pythonを入力してください...

中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか? 中間の読書にどこでもfiddlerを使用するときにブラウザによって検出されないようにするにはどうすればよいですか? Apr 02, 2025 am 07:15 AM

fiddlereveryversings for the-middleの測定値を使用するときに検出されないようにする方法

あるデータフレームの列全体を、Python内の異なる構造を持つ別のデータフレームに効率的にコピーする方法は? あるデータフレームの列全体を、Python内の異なる構造を持つ別のデータフレームに効率的にコピーする方法は? Apr 01, 2025 pm 11:15 PM

PythonのPandasライブラリを使用する場合、異なる構造を持つ2つのデータフレーム間で列全体をコピーする方法は一般的な問題です。 2つのデータがあるとします...

uvicornは、serving_forever()なしでhttpリクエストをどのように継続的に聞いていますか? uvicornは、serving_forever()なしでhttpリクエストをどのように継続的に聞いていますか? Apr 01, 2025 pm 10:51 PM

UvicornはどのようにしてHTTPリクエストを継続的に聞きますか? Uvicornは、ASGIに基づく軽量のWebサーバーです。そのコア機能の1つは、HTTPリクエストを聞いて続行することです...

プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は? プロジェクトの基本と問題駆動型の方法で10時間以内にコンピューター初心者プログラミングの基本を教える方法は? Apr 02, 2025 am 07:18 AM

10時間以内にコンピューター初心者プログラミングの基本を教える方法は?コンピューター初心者にプログラミングの知識を教えるのに10時間しかない場合、何を教えることを選びますか...

Investing.comの反クローラーメカニズムをバイパスするニュースデータを取得する方法は? Investing.comの反クローラーメカニズムをバイパスするニュースデータを取得する方法は? Apr 02, 2025 am 07:03 AM

Investing.comの反クラウリング戦略を理解する多くの人々は、Investing.com(https://cn.investing.com/news/latest-news)からのニュースデータをクロールしようとします。

See all articles