[Algorithm] 이분 탐색(Binary Search)

정의

정렬되어 있는 리스트에서 어떠한 데이터를 찾을 때,

순차 탐색과 같이 모든 값을 대조하여 찾는 것이 아니라

탐색 범위를 절반씩 줄여가면서 찾는 방법입니다.

 

작동원리

예를 들어서 1,2,3,4,5,6 가 들어있는 배열에서 찾으려고 하는 값이 6이라고 한다면

배열의 중간 값(= mid)인 3과 6을 비교합니다.

 

6은 3보다 크기 때문에 3보다 작은 값들과는 비교할 필요가 없으므로

3보다 큰 값들인 4,5,6 중에서 대조를 합니다. 

 

다시 이 중의 중간 값인 5와 6을 비교하고 6은 5보다 크므로 5보다 작은 값들과는 비교할 필요가 없습니다.

이제 5보다 큰 값과 비교하면 되는데 5보다 큰 값은 이제 6밖에 없으므로 결과를 찾은 것입니다.