ナビゲーションアルゴリズム1-完全ナビゲーション/二分ナビゲーション

4566 ワード
Binary Search brute force テキストリンク

1.ナビゲーション


:大量のデータで必要なデータを検索します.
  • フルナビゲーション
  • 二分探索
  • 深度優先ナビゲーション
  • 幅優先ナビゲーション
  • 文字列ナビゲーション、KMP、BMなど...

    • 1）完全ナビゲーション

  • コンピュータの高速計算能力を利用して、可能な限り
    • をナビゲートする.
  • 無条件の答えですが、効率が最も低いアルゴリズム
    • 例)カードを含むリストtrumpで8番カードを検索する

    (1)繰り返し文の使用

    def solution(trump):
    for i in range(len(trump)):
    	if trump[i] == 8:
            return i
    return i

    (2)再帰関数の使用

    def solution(trump, loc):
    if trump[loc] == 8:
    	return loc
    else:
    	return solution(trump, loc+1)

    2）二分探索（Binary Search）

  • 並べ替えリストで特定の値の位置を検索するアルゴリズム
    • 検索する値より大きいか小さいかを比較するには、
  • の中間値を選択します.
    先ほどと同じカードを探す8-二分ナビゲーションを使う
    def solution(trump):
    left = 0
    right = len(trump)-1
    
    while (left <= right):
        mid = (left+right)//2
        if trump[mid] == 8:
            return mid
        elif trump[mid] < 8:
            left = mid + 1
        elif trump[mid] > 8:
            right = mid - 1
    return mid
    • [アルゴリズム]LeetCode-Reverse Integer
    特定のアプリがインストール済みかチェックする