[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

[ Contents ] 1. 이진탐색 (Binary Search, 이분탐색) 이진탐색: 정렬된 자료를 절반씩 나누어서 탐색하는 방법 오름차순(또는 내림차순)으로 정렬된 자료에서 사용합니다.

찾고자 하는 숫자와 자료의 중간값과 비교하여 탐색 범위를 절반씩 줄여갑니다. 찾고자 하는 수보다 작으면 작은 쪽을, 크면 큰 쪽을 찾습니다.

이진탐색 과정 1) 찾는 값과 중앙값을 비교합니다. 2) 중앙값과 같다면 탐색 종료. 작다면 작은 쪽을 크다면 큰 쪽을 찾습니다. 3) 값을 찾을 때까지 1, 2 과정을 반복합니다.

예를 들어 32를 찾고자 한다면, 중앙값인 63과 값을 비교합니다. 63보다 작으니, 작은 쪽에서 찾습니다. 12, 32, 41의 중앙값은 '32'입니다. 32를 찾았으므로 종료합니다. 2. 이진탐색.....