정리하기 위한 블로그 정리하기 위한 블로그

https://www.acmicpc.net/blog/view/109 이분 탐색(Binary Search) 헷갈리지 않게 구현하기개요 이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다. 이분 탐색 문제를 풀다보면 탈출 조건으로 lo www.acmicpc.net 이분 탐색 구현할 때마다 항상 헷갈려서 시간이 걸리게 되는데, 위의 글 읽고 정리해본다. 구현 방법 먼저 결정 문제 설정과 분포 파악해야한다. 문제마다 결정 문제가 다른데 이를 먼저 설정하고, 결정 문제에 따른 True, False 결과의 분포를 생각해본다. 예를 들면 1~50번의 카드 중 28번 카드를 찾는다고 하자. 1~50번의 카드를 v[i] 찾는 카드를 val 이라 할 때, 결정 문제는 val  lo+1 동안 범위를..