バイナリナビゲーション

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

リスト内の特定のデータを検索するには、前のデータを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)