これがPython Chep 7によるエンコードテストです.バイナリ・ナビゲーション1.範囲を半分に縮小する探索


1.範囲を半分に縮める探索


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

  • シーケンスは、リスト内の特定のデータを検索するために、前からデータを個別にチェックする方法を研究する.
  • リスト型ではcount()メソッドを使用して特定の値を持つ要素の個数を計算すると、内部でも順次検索が行われる.
  • # 순차 탐색 소스코드 구현
    def sequential_search(n, target, array):
    	# 각 원소를 하나씩 확인하며
        for i in range(n):
        	# 현재의 원소가 찾고자 하는 원소와 동일할 경우
            if array[i] == target:
            	return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 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 Alex
    エレメント数が最も少ない文字列を入力してください.スペースに区切ります.
    -> Jason Nick Alex William Ray
    -> 3

    2)バイナリナビゲーション:半開きナビゲーション

  • バイナリ検索では、アレイ内のデータをソートする必要があるアルゴリズムです.データはランダムでは使用できませんが、ソートされている場合は、データをすばやく見つけることができます.
  • バイナリナビゲーションの特徴は、ナビゲーション範囲を半分に縮小し、データをナビゲートできることです.
  • 再帰関数を用いて実現されるバイナリプローブコード
  • # 이진 탐색 소스코드 구현(재귀 함수)
    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)
    バイナリナビゲーションソースコード
  • は、繰り返し文によって実現される
    # 이진 탐색 소스코드 구현(반복문)
    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)

    3)木資料構造


    ノードと
  • ノードとの接続を示す、ノードは情報の一部であり、ある情報を有するオブジェクト
  • と理解できる.
  • ツリーデータ構造の特徴
  • ツリーは、親ノードと子ノードの関係を表します.
  • ツリーの最上位ノードをルートノードと呼びます.
  • ツリーの最下層ノードを端末ノードと呼ぶ.
  • ツリーから一部を取り外しても、ツリー構造であり、サブツリーとして使用されます.
  • ツリーは、ファイルシステムと同様に、階層化およびソートされたデータを処理するのに適している.
  • 4)バイナリナビゲーションツリー

  • バイナリナビゲーションによって設計された有効なナビゲーション可能なデータ構造.
  • プロパティ
    左サブノードが
  • より小さい親ノード
  • 右側の子ノードは
  • の親ノードより大きい.