バイナリ検索|バイナリ検索

大量のデータを一度にブラウズするアルゴリズム

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

N個のデータがある場合、最大でN回の比較演算が必要となるため、最悪の場合、時間複雑度はO(N)となる.

バイナリナビゲーションの時間的複雑さ:O(logn)

1つのステップを経るたびに、確認された要素は半分に減少します.時間的複雑度はO(logn)である.

バイナリ検索|バイナリ検索

実施方法

再帰関数

複文

データ位置を表す変数:start(始点)/mid(中点)/end(終点)
コア|検索するデータと中間位置にあるデータを繰り返し比較して、必要なデータを検索
1)再帰関数

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, start)

n, target = map(int, input().split())
array = list(map(int, input().spllit()))

result = binary_search(array, target, 0, n-1)
if result == None:
	print("해당 원소 없음")
else:
	print(result + 1)

2)繰り返し文

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 = map(int, input().split())
array = list(map(int, input().spllit()))

result = binary_search(array, target, 0, n-1)
if result == None:
	print("해당 원소 없음")
else:
	print(result + 1)

コアコード

elif array[mid] > target:
	end = mid - 1

中間点の要素値がターゲットより大きい場合は、ターゲットがないため、中間点の右側を表示する必要はありません.したがって、端点は中点左側(mid-1)インデックスとして指定されます.
つまり、右端のデータが失われています!

else:
	start = mid + 1 

中間点の要素値がターゲットより小さい場合、中間点の左側にはターゲットがないため、表示する必要はありません.したがって、始点を中点右側(mid+1)インデックスとして指定します.
つまり、左のデータがなくなった!

コーディングテストバイナリナビゲーション

-広範囲のナビゲーションの問題

処理するデータの数や値が非常に大きい場合は、O(logn)の速度を速めるアルゴリズムを考えなければ問題を解決できないことが多い.

入力データの多い問題の解決

Input()関数を使用すると、動作速度が遅いためエラーと判定されます.
この場合、sysライブラリのreadline()関数を使用すると、タイムアウトを回避できます.

import sys
input_data = sys.stdin.readline().restrip()

注意事項

rstrip()関数を呼び出さない場合、readline()を入力すると、エンティティは改行で入力されますが、スペース文字は削除されません.だから必ず呼んでください.

習った本|これがPythonでコードテスト