Binary Search

2251 ワード

バイナリ検索は、配列内部のデータをソートする必要があるアルゴリズムです.データが並べ替えられていれば、すぐにデータが見つかるのが特徴です.ブラウズ範囲を半分に縮小し、データをブラウズします.
バイナリナビゲーションでは、位置を表す変数の始点、終点、中点を3つ使用します.検索するデータと中間位置にあるデータを繰り返し比較し,所望のデータを探すのがバイナリ探索過程である.
バイナリ探索の時間的複雑度はO(logn)であり,確認されるたびに元素数が半分に減少するためである.バイナリ検索を実現する方法は、再帰関数と重複文の使用の2つです.
def binary_search(array, target, start, end):
	if start > end:
    	return None
    mid = (start + end) // 2
   	# 찾은 경우 중간점 index return
    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 = 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
      # 찾은 경우 index return
      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)

ツリーデータ構造


データベースは内部でビッグデータを処理するのに適したツリー構造を採用し、常にデータをソートします.したがって、バイナリ検索のような方法でデータをすばやく参照することができます.ツリー構造は、ノードとノードの接続費を表します.ノードは情報の単位として,任意の情報を持つオブジェクトとして理解できる.ツリー構造には、次の特徴があります.
  • ツリーは、親ノードと子ノードの関係
  • として表す.
  • ツリーの最上位ノードをルートノード
  • と呼ぶ.
  • ツリーの最下層ノードを端末ノード
  • と呼ぶ.
  • の木から一部を外すとしても、サブツリー
  • と呼ばれる木構造である.
  • ツリーは、ファイルシステムと同様に階層化、ソートされたデータの処理に適しています.

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


    ツリーの資料構造の中で,最も簡単な形式はバイナリ検索ツリーである.バイナリ検索ツリーは、バイナリ検索操作のために構築された効率的な検索可能なデータ構造です.バイナリ探索ツリーには、次のような特徴があります.
    左サブノードが
  • より小さい親ノード
  • 右サブノードが
  • より大きい親ノード

  • バイナリツリーは、左側のサブノード<親ノード<右側のサブノード>が作成されている場合にのみ作成されます.

    Reference


    これがPythonのコードテストです