[ARGORITHM]バイナリナビゲーション

シーケンスナビゲーションvsバイナリナビゲーション

シーケンシャルナビゲーション:特定のデータ

を検索するために前から1つずつデータをチェックする.

バイナリナビゲーション:ソートされたリストで、ナビゲーション範囲を半分に縮小します.
始点中点端点を利用して、ナビゲーションの前提は位置合わせのデータ

である.

バイナリナビゲーションの時間的複雑さ

のナビゲーション範囲をステップ2毎に分けることに等しい->演算回数log(2)Nに比例する

時間複雑度O(logn)

シーケンシャルナビゲーションの時間的複雑度はO(N)

である.

シーケンスナビゲーションソースvsバイナリナビゲーションソース

シーヶンスナビゲーション

## 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소 하나씩 확인
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i]==target:
            return i+1 # 현재 위치 반환
    return -1

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0])
target = input_data[1]

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")  
array = input().split()

# 순차 탐색 수행 결과
print(sequential_search(n, target, array))

作成する要素の数を入力し、スペースを入力して検索する文字列を入力します.
5 aa
エレメント数が最も少ない文字列を入力してください.スペースに区切ります.
d f r aa s
4
バイナリナビゲーション

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)

5 3
1 2 3 4 5
3
バイナリナビゲーション

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 을 입력 받기
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)

5 3
1 2 3 4 5
3

バイナリナビゲーション

エンコードテストのバイナリナビゲーションタイプ

バイナリ検索の問題は,検索範囲が広い場合に検索を仮定することが多い.
探索範囲が2000万を超えるなら、バイナリで近づく方法を考えてみましょう!

クイック入力
バイナリ検索タイプ入力データが多いか、検索範囲が広い.
たとえば、データが1000万を超える場合や、ナビゲーション範囲が1000億を超える場合は、バイナリナビゲーションを試してみましょう.
データが多すぎてinput()速度が遅すぎてタイムアウトと判定された場合はreadline()を使用してください!

import sys
input_data = sys.stdin.readline().rstrip()
print(input_data)

readline()入力を受信すると、入力後に改行文字で入力されます.
rstrip()を呼び出してスペース文字を削除します!

ツリーデータ構造

データベースシステムまたはファイルシステムにおける大量のデータ管理に使用されるグラフィック資料構造の一種.
このツリー構造は,バイナリ探索のような手法を用いて探索を迅速に実行する.

ツリーの特徴

は、親ノードと子ノードの関係

を表す.

最上位ノード=親ノード

最下位ノード=サブノード

の木から一部を外すとしても、木構造はサブツリー

と呼ぶ.

階層化および並べ替えに適したデータ

バイナリナビゲーションツリー

ツリーデータ構造の中で最も簡単な形式

右側サブノード>親ノード>左側サブノード

サブノードが存在しない前に要素が見つからない場合、バイナリ・ナビゲーション・ツリーに要素はありません.

パラメトリックメジャー

最適化問題を決定問題(yesまたはno)に変換して

を解決する.

問題

の範囲で,条件を満たす最大値を探す最適化問題をパラメトリックにより解いた.

二分ナビゲーションとパラメトリック検索

이분 탐색は、ターゲットが配列中に存在するかどうかと存在する位置を教えてくれます.
targetと完全に一致する値が存在しない場合は、パラメトリックプログラムを使用して最適な値を探すことができます.파라메트릭 서치は、最適化された問題を決定問題に変換するアルゴリズムである.

最適化問題:複数の問題の答え、そのうち基準に基づいて最適な答えを探す問題

決定問題
最適化問題の状況は無限であり,決定問題には2つの答えしかない.
問題を最適化して問題を特定するレシピに変更
1.「一番いい答えは何ですか?」このような最適化問題は「xより良い答えはありますか?」「意思決定問題」の形式に変更
2.意思決定問題を解決する簡単な方法を探す
3.内部利用決定問題の作成이분탐색アルゴリズムBinary Search와 Parametric Search의 차이점Binary Searchでは、配列にXに一致する値が見つかった場合、関数をすぐに終了し、位置を返します.
Parametric Searchは、関数を終了するのではなく、表示する配列がなくなるまでブラウズを続けます.

参考にしました。

https://junk-s.tistory.com/35

https://hbj0209.tistory.com/146