이분 탐색이란?

• 이분 탐색은 이진 탐색, Binary Search 라고도 하며, 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법입니다.

• 이진 탐색은 정렬된 배열에서 원하는 값을 찾아내는 알고리즘으로, 정렬된 배열의 중앙값과 찾고자 하는 값을 비교해 배열의 크기를 절반씩 줄이면서 대상을 찾는 방식입니다.

이분 탐색 예시

먼저 1부터 100까지 오름차순으로 들어 있는 배열에서 77을 찾는 예시를 보자.

1. 먼저 배열의 중간 값인 50과 77을 비교한다. 77이 더 크므로 50보다 작은 왼쪽 배열은 볼 필요가 없으므로 버리고 50보다 큰 배열만 남긴다.

2. 50 부터 100까지의 배열의 중간 값인 75와 77을 비교한다. 75보다 77이 크므로 75보다 작은 배열은 버리고 75 이상 100이하 배열만 남긴다.

3. 75부터 100까지의 배열의 중간 값인 87과 77을 비교한다. 87이 더 크므로 87보다 큰 배열은 버리고 75이상 87이하 배열만 남긴다.

4. 75부터 87까지의 배열의 중간 값인 81과 77을 비교한다. 81이 더 크므로 81보다 큰 배열은 버리고 75이상 81이하 배열만 남긴다.

5. 75부터 81까지의 배열의 중간 값인 78과 77을 비교한다. 78이 더 크므로 78보다 큰 배열은 버리고 75부터 78까지의 배열만 남긴다.

6. 75부터 78까지의 배열의 중간 값인 76과 77을 비교한다. 76이 더 작으므로 76보다 작은 배열은 버리고 76부터 78까지의 배열만 남긴다.

7. 76부터 78까지의 배열의 중간 값인 77과 찾는 수인 77을 비교한다. 찾는 수를 찾았으므로 종료한다.