이분 탐색의 처리를 차분히 쫓아 본다

개요

atcoder 에서도 빈출 테마인 이분 탐색에 관한 내용입니다.

소개

이분 탐색은 비교적 단순한 방법이지만, 구현으로 넘어지는 경우가 많지 않을까 느끼고 있습니다.

이분 탐색에서의 처리 흐름을 차분히 이해하는 것을 목적으로 이분 탐색 샘플의 문제를 하나 다루어 구현시의 처리를 하나씩 따라가며 이분 탐색에 사용되는 변수의 이해를 깊게 함을 목적입니다.
(다음 번, 콘테스트에서 2분 탐색이 출제되었을 때의 구현에 곤란하지 않게...)
이분 탐색 알고리즘의 설명 등은 이쪽 등의 다른 기사를 참조하십시오.

htps : // 코데지네. jp/아리치ぇ/에서 싶은 l/9900? p=2

샘플 문제

경쟁 프로 전형 90문의 제1문의 케이스를 다룹니다.

001 - Yokan Party (★4)

h tps // 아 t 여기 r. jp / sts / ty pika l90 / sks / ty pika l90_
(문제/정중한 해설을 작성해 주시는 분에게 감사드립니다.)

코드(py)

※ 기본적으로 이쪽의 c++의 코드를 python 에 고쳐 쓴 코드가 되고 있습니다.
htps : // m / 869120 / ms / 1b2 5f0f07fd927 44 9

Main.py

n, l = map(int, input().split())
k = int(input())
a = list(map(int, input().split()))

def solve(mid):
    """ ある羊羹の切れ目の間隔の最小値候補が条件を満たすか否かを判定する
    Args:
        mid (int): [羊羹の切れ目の間隔の最小値候補]
    Returns:
        boolean: [判定対象のindex が条件を満たすかどうか]
    """
    tmp_val = 0 # 切った羊羹の長さ
    cut_cnt = 0 # 羊羹を切る数
    for i in range(n):
        if a[i] - tmp_val >= mid and l - a[i] >= mid:
            cut_cnt += 1
            tmp_val = a[i]
    if cut_cnt >= k:
        return True
    else:
        False
right = l
left = 0
while right - left > 1:
    mid = (right + left) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
print(left)

다음의 샘플 케이스로 생각합니다.

7 45
2
7 11 16 20 28 34 38

while 처리 할 left, right, mid의 각 변수의 값 전이

left(조건을 만족하는 범위)
mid (각 단계에서의 판정 대상)
right(조건을 만족하지 않는 범위)


0

22⤷
45

0
⤶11

22

11

16⤷
22

11

13⤷
16

11
⤶12

13

12
12
13


각 mid의 값을 left, 혹은, right 로 나누고 있는 것처럼 보이네요.
left는 조건을 만족하는 최대 값입니다. > 즉, 이 문제의 대답이 되고 있습니다.
반면 right는 조건을 충족시키지 않는 최소값입니다.

마지막 while 문을 처리 할 때,

right = 13

left = 11

mid = 12

right - left = 2> 1부터 while 문을 계속합니다.

while 문이 끝날 때,

right = 13 ... (조건을 만족하지 않는 최소값)

left = 12 ... (☆ :이 샘플 케이스의 대답)

mid = 12

right - left = 1부터 while 문을 종료합니다.

따라서 결국,

left는 조건을 만족하는 최대 값을 저장하고

right에 조건을 만족하지 않는 최소값이 포함되어 있음을 알 수 있습니다.

처리 흐름

요약

단순히 이진 탐색을 구현하는 것만으로는, 둘러싸는 식 이분 탐색이라고 불리는 구현의 유파 [링크]나 Python의 표준 라이브러리의 bisect 모듈을 사용해 구현할 수도 있겠지요.

자신 나름의 이분 탐색의 실장 방법을 착용하는 것이 제일 자신의 힘이 될까라고 생각합니다.