[データ構造/アルゴリズム]線形構造ナビゲーション

4309 ワード
データ構造とアルゴリズム テキストリンク
せんけいこうぞうデータブラウズほう
📌 シーヶンスサーチ
必要なデータを検索するために、データを最初から最後まで1つずつ比較するアルゴリズム
  • .
  • 単純だが非効率
  • 平均(n+1)/2回比較;最悪の場合はn回比較;時間複雑度O(n)
  • 一方向ナビゲーション、線形ナビゲーションとも呼ばれる
    📌 にぶんたんさく
  • 配列配列中のデータを検索するアルゴリズム
  • は、場合によってはシーケンシャルナビゲーションよりも高速です.
  • は、すべてのデータを表示するのではなく、ナビゲーション範囲を半分に縮小するナビゲーション方法
    • である.
  • からナビゲーションを開始する特性
  • 時間複雑O(log 2 N)
    • 二分航法Ex)アレイ13 4 7 8 13 17において「8」の位置が検索されたとする.
    アレイ:1 3 4 7 8 13 17

  • 中間値7を選択
    1 3 4 7 8 13 17

  • 7<8、大きな数字を右に移動
    7 8 13 17

  • 7～17のアレイから13を選択
    7 8 13 17

  • 13>8、小さい数字を左に移動
    7 8 13

  • 7と13の中間に位置する8
    7 8 13

  • 8=8、5番目の配列なので、答えは5です.
  • は、すべての入力コードが昇順に並べられることを要求する.
    • //헤더 부분
int solve(int,int);
//소스 부분
int A[500]; //총 500개까지 담을 수 있는 배열에서 탐색.
int k; //탐색할 값.

int solve(int s, int e);
{
    int m;
    while(e-s>=0)
    {
        m=(s+e)/2; 값이 있을 가능성이 있는 값의 가운데 값.
        if(A[m]==k)
            return m+1; //그 값이 만약 탐색할 값이면 그 위치를 리턴.
        if(A[m]<k) s=m+1; //만약 A[m]이 작으면 좀 더 큰 값들이 있는 오른쪽이 탐색되도록 변경.
        else e=m-1; //아까와 정반대.
    }
    return -1; //찾는 값이 없을 경우 -1을 준다.
}
    ソース:https://satisfactoryplace.tistory.com/39
    MaterialDesignシリーズ記事(十七)Behaviorに関する質問
    ベンダー:スマートShopify選択肢