バイナリナビゲーション

11695 ワード
大学生。 アルゴリズム#アルゴリズム# テキストリンク

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



  • リスト内の特定のデータを検索するには、前のデータを1つずつチェックします.

  • ソートされていないリストでデータを検索するには

  • その利点は、リストのデータがどんなに大きくても、十分な時間さえあれば、必要な要素を見つけることができるということです.

  • したがって、シーケンスナビゲーションは、名前順にデータをナビゲートすることを意味します.実現するのもとても簡単です!
    • def sequential_search(n, target, array):
	for i in range(n):
		if array[i] == target:
			return i + 1

print("생성할 원소 개수를 입력한 다음 한 칸을 띄고
찾을 문자열을 입력하세요")

input_data = input().split()
n = int(input_data[0])
target = input_data[1]

print("원소 개수만큼 문자열 입력")
array.split()

print(sequential_search(n, target, array))
    最悪の場合,時間複雑度O(N)−データ数がNの場合,最大N回の比較演算が必要となる

    探索する



  • ふたつに分けて探求する

  • バイナリ・ナビゲーションは、アレイ内のデータをソートするアルゴリズムです.

  • データの閲覧範囲を半分に縮小
    • 3つの変数を使用します:範囲の始点、終点、中点

  • 検索するデータと中間位置のデータを繰り返し比較

  • 元素の個数を半分に減らしてみると,時間的複雑さはO(logn)である.

    💨 バイナリナビゲーションを実現する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 = 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 = 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)
    Javaベースのプログラミング/演算子
    Codility: CyclicRotation