これは私がナドンビンで聞いた内容に基づいて勉強した投稿です.

✔バイナリ探索は何ですか?

これは、ソートされたリストで検索範囲を半分に縮小する方法です.ブラウズ範囲が半分に縮小されたため、ログ時間の複雑さが高くなります.バイナリ・ナビゲーションを実行するには、ナビゲーション範囲を設定するために、開始点、終了点、および中間点のナビゲーション・ポイント(インデックス)を指定する必要があります.

👉 トラブルシューティングプロセス

# 이진 탐색 소스코드 구현 (재귀 함수)
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) #끝점 = 중간인덱스-1
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end) #시작점 = 중간인덱스+1

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1) #(array, target, start, end)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

延辺朝鮮族捜索庫イコテ

対左(a,x):配列aにxを挿入する最も左側のインデックス

を返し、ソート順を維持します.

対右(a,x):配列aにxを挿入する最も右のインデックス

を返し、ソート順を維持します.

👉 時間の複雑さ

各ステップの探索範囲は1/2に縮小され,演算回数はlog⁡Nに比例する.したがって,時間的複雑度はO(logn)である.

✔問題1：トッポッキ作り

カッターで高さ(H)を指定すると、Hより長いカッターは切り落とされ、Hより小さいカッターは切り落とされません.例えば、カッターの高さが15 cmの場合、19、14、10、17 cmの餅は4、0、0、2 cmに切られ、客は6 cmの長さを持っていく.お客様が要求する長さが総Mである場合、少なくともMの餅を得るために、カッターで設定可能な高さの最値を求める.

👉 トラブルシューティングプロセス

端点と始点をバイナリサーチで移動し、Mが現れるまでHを調整します.
1.
2.
3.Mが現れるまで、上記の手順を繰り返します.

# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array) #가장 긴 떡의 길이

# 이진 탐색 수행 (반복적)
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때의 떡볶이 양 계산
        if x > mid:
            total += x - mid
    # 떡볶이 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡볶이 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

print(result)

✔問題2：ソート順から特定数量の個数を求める

N個の要素を含む数列を昇順に並べます.このときの数列にxが現れる回数を求める.(時間的複雑度はO(logn)である.)

👉 トラブルシューティングプロセス

時間的複雑さを満たすためには,バイナリ検索が必要である.xが出現する最初の位置、最後の位置(xの最後の位置-xの最初の位置)+1を計算すると、xが出現する回数を求めることができる.
あるいは、対分を使用してxを挿入できる最初の位置または最後の位置を探し出す.

from bisect import bisect_left, bisect_right

# x 개수 찾기
def count_by_range(array, left_value, right_value):
	right_index = bisect_right(array, right_value) #6
    left_index = bisect_left(array, left_value) #2
    return right_index - left_index #4
    
n, x = map(int, input().split())
array = list(map(int, input().split()))

#값이 [x, x] 범위에 있는 데이터 갯수
count = count_by_range(array, x, x)

if count == 0:
	print("해당 원소는 없습니다.)
else:
	print(count)