이분 탐색(binary search)란, 어떤 배열과 찾고자 하는 수가 있을 때, 찾고자 하는 범위를 절반씩 좁혀가며 빠르게 해당 값의 위치를 찾아내는 알고리즘입니다. 알고리즘 문제에서 자주 등장하는 대표적인 탐색 기법으로, 단순한 정렬 배열 탐색부터, 경계값 찾기, 응용 문제까지 매우 다양한 형태로 출제됩니다. 매 반복마다 검색 범위를 절반으로 줄이기에 O(log n)의 시간 복잡도를 가집니다. 다만, 값의 대소를 비교하며 범위를 잡기에 배열이 반드시 정렬됨을 전제로 합니다.구현: 반복 vs. 재귀이분 탐색은 먼저 시작 인덱스와 끝 인덱스를 잡고, 그 둘의 중간 (또는 안 나눠떨어질 경우 한 칸 왼쪽) 인덱스를 잡는 것으로 시작합니다. 그리고 정확한 값의 인덱스를 찾을 때까지 시작, 중간, 끝 인덱스를..