[アルゴリズム]バイナリナビゲーションアルゴリズム

バイナリ・ナビゲーション・アルゴリズム:リスト内でデータをすばやくナビゲートするアルゴリズム(前提条件:整列データの使用)

1.シーケンシャルナビゲーション

1）定義と特徴

リスト内の特定のデータを検索するには、前から順にデータをチェックします:

は、通常、並べ替えられていないリストでデータを検索する場合に

を使用する必要がある.
その利点は、

リストのデータがどれだけ大きくても、十分な時間さえあれば、欲しいデータを見つけることができるということです.

2）探索過程

< 'orange' 찾기 🍊 >
Data = ['banana', 'strawberry', 'orange', 'apple', 'tomato']

✔ 1단계. 첫 번째 데이터를 확인한다.
➡ 첫 번째 데이터는 banana이다.  banana != orange 이므로 다음 데이터로 이동한다.

✔ 2단계. 두 번째 데이터를 확인한다.
➡ 두 번째 데이터는 strawberry이다.  strawberry != orange 이므로 다음 데이터로 이동한다.

✔ 3단계. 세 번째 데이터를 확인한다.
➡ 세 번째 데이터는 orange이다. 이는 우리가 찾고자 하는 data이다.
   따라서 세 번째 데이터에서 탐색을 마친다.

👉 このように,順序探索は名前のように順次データを探索することを意味する.
👉 リスト内のデータに1つずつアクセスし、特定の文字列と同じかどうかを確認します.
👉 本当によく使われており,count()法も内部で順序探索を行っている.

3）Pythonコードの実現

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i+1   # 현재 위치 반환(인덱스는 0부터 시작하므로 +1)


input_data = input('생성할 원소의 개수와 찾을 문자열을 입력하세요(띄어쓰기로 구분)').split()
n = int(input_data[0])  # 원소(데이터)의 개수
target = input_data[1]  # 찾고자 하는 문자열

array = input('앞서 적은 원소의 개수만큼 문자열을 입력하세요(띄어쓰기로 구분)').split()

print(sequential_search(n, target, array))

2.探索バイナリ

1）定義と特徴

これは

データを二つの半分に分けて探索するアルゴリズムである.範囲を半分に縮小

データがランダムな場合は使用できません.

使用するには、

アレイ内のデータをソートする必要があります.クイックナビゲーション
3つの

変数(始点、終点、中間点)を使用して、検索するデータと中間点の位置にあるデータを繰り返し比較し、希望するデータを探します.

2）探索過程

< 정렬된 10개의 데이터 중에서 숫자 4 찾기 >
data = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

✔ 1단계. 시작점과 끝점을 확인한 다음, 둘 사이에 중간점을 정한다.
➡ 시작점: data[0]=0, 끝점: data[9]=18, 중간점: data[4]=8
➡ 중간점을 정할 때, data의 개수가 짝수인 경우는 나머지를 버림처리한다.


✔ 2단계. 중간점의 데이터와 찾으려는 데이터를 비교하고 이동시킨다.
➡ 중간점이 8이고, 찾으려는 데이터는 4이다. 따라서 중간점 이후의 데이터는 볼 필요가 없다.
➡ 끝점을 data[4]의 바로 앞인 data[3]으로 이동시킨다.
➡ data = [0, 2, 4, 6]으로 변경되었다.


✔ 3단계. 시작점, 끝점, 중간점을 확인한다.
➡ 시작점: data[0]=0, 끝점 : data[3]=6, 중간점 : data[1]=2


✔ 4단계. 중간점의 데이터와 찾으려는 데이터를 비교하고 이동시킨다.
➡ 중간점 데이터: 2 < 찾으려는 데이터: 4 이므로 2 이하인 데이터는 확인할 필요가 없다.
➡ 시작점을 중간점 다음인 data[2]로 변경한다.
➡ data = [4, 6]으로 변경되었다.


✔ 5단계. 시작점, 끝점, 중간점을 확인한다.
➡ 시작점: data[0]=4, 끝점: data[1]=6, 중간점: data[0]=4
➡ 중간점 데이터: 4 = 찾으려는 데이터: 4 이므로 여기서 탐색을 종료한다.

👉 バイナリナビゲーションの始点/終点/中点は毎回変化するので、移動するたびに確認します.
👉 その利点は,確認するたびに要素数が半分に減少することである.
👉 '位置決めデータ比較位置決め移動フェーズで行います.
📢 データがソートされている場合のみ使用可能

3-1)Pythonコード|メソッド1を実装する.さいきかんすう

def binary_search(array, target, start, end):
    if start > end:
        return None
    
    # 중간점 위치 찾기
    mid = (start + end) // 2
    
    # 데이터 찾은 경우
    if array[mid] == target:
        return mid
    
    # 중간점의 값 > 찾으려는 값
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    
    # 중간점의 값 < 찾으려는 값
    else:
        return binary_search(array, target, mid+1, end)
    
# 원소의 개수(n)와 찾으려는 값(target) 입력받기    
n, target = list(map(int, input().split()))

# 전체원소 입력받기
array = list(map(int, input().split()))

# 이진탐색 수행 결과
result = binary_search(array, target, 0, n-1)

if result == None:
    print('원소가 존재하지 않습니다.')
    
else:
    print(result+1)

3-2)Pythonコード|メソッド2を実装する.複文

def binary_search(array, target, start, end):
    while start <= end: # 시작점 <= 끝점인 경우에만 반복문 실행
        mid = (start + end) // 2
        
        # 데이터 찾은 경우
        if array[mid] == target:
            return mid
        
        # 중간점의 값 > 찾으려는 값
        elif array[mid] > target:
            end = mid-1
            
        # 중간점의 값 < 찾으려는 값    
        else:
            start = mid+1
            
    return None
    
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
    print('원소가 존재하지 않습니다.')
    
else:
    print(result+1)

3.バイナリ探索ツリー

この真探索木に言及する前に,木の資料構造を簡単に理解しておきましょう.

1)ツリー構造

ノードとノードの接続として表現される.(ノード:情報単位のオブジェクト)

ツリーは、親ノードと子ノードの関係を表します.

ツリーの最上位ノードをルートノードと呼びます.

ツリーの最下層ノードを端末ノードと呼ぶ.

木から一部を外しても、サブツリーと呼ばれるツリー構造です.

ツリーは、ファイルシステムと同様に、階層化およびソートされたデータを処理するのに適している.

2）バイナリプローブツリーの定義

ツリーの資料構造の中で最も簡単な形式です.
バイナリ探索ツリーは,バイナリ探索を機能させるために設計された有効な探索が可能な資料構造である.

3）特徴

左側のサブノードは

の親ノードより小さい.

右側の子ノードは

の親ノードより大きい.
e左側サブノード<親ノード<右側サブノード

4）動作原理

バイナリプローブツリーで検索された要素は、下図に示すように37です.

バイナリ・ナビゲーションはルート・ノードからアクセスを開始します.
ルートノードは「30」で、検索された要素は「37」です.
eしたがって,30未満の左側ノードを調べる必要はなく,右側ノードのみにアクセスする.

右側の子ノード「48」が今度は親ノードになります.
»親ノード:48>検索する要素:37
eしたがって、48より大きい右側ノードをチェックする必要はなく、左側ノードにアクセスする.

現在アクセスしているノードは「37」であり、検索された要素値も37です.
それで探索を終了する.

👉 ルートノードから左サブノード、右サブノードに移動し、繰り返しアクセスします.
👉 サブノードがない前に要素が見つからない場合は、バイナリプローブツリーに要素がありません.
📢 バイナリナビゲーションツリーを実装するよりも、動作原理を理解することが重要です.