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

せんけいこうぞうデータブラウズほう
📌 シーヶンスサーチ
必要なデータを検索するために、データを最初から最後まで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