[알고리즘] 이분탐색 헷갈리지 않기
저는 이분탐색 문제를 풀 때마다 헷갈립니다. . 탈출 조건 중 어느 걸 선택해야 할지, while 문도 범위를 매번 정확히 하지 않은채 문제를 풀곤 했는데요. 오늘 헷갈리지 않게 구현하는 방법을 정리하려고 합니다 ! 이분탐색 결정 문제의 답이 이분적일 때 사용할 수 있는 탐색 기법입니다. 이 때, 결정 문제란 답이 Yes or No인 문제를 말합니다. 예를 들어, 1 ~ 50까지의 오름차순 정렬된 카드 더미(v[])에서 val번 카드를 찾는 문제를 예시로 들게요. 이 경우, 결정 문제를 "v[i] >= val인가 ?"로 잡으면 결정 문제는 i가 증가함에 따라 F, F, ... F, T, T, ... 와 같이 분포하게 됩니다. 이 때, 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 처음 결정..
2022. 11. 25.
