2이분 탐색 알고리즘

 

다시 문제로 돌아와서 정렬된 리스트에서 특정 값을 찾으려면 어떻게 해야 할까요?

다음 예를 통해 이분 탐색의 원리를 배워 봅시다.

 

리스트: [1, 4, 9, 16, 25, 36, 49, 64, 81]

찾는 값: 36

 

1 | 먼저 전체 리스트의 중간 위치를 찾습니다. 위치 번호 4가 리스트의 중간 위치이고, 중간 위치 값은 25입니다.

2 | 찾는 값 36과 중간 위치 값을 비교합니다. 36 > 25이므로 36이 리스트 안에 있다면 반드시 25의 오른쪽에 있어야 합니다. 즉, 리스트에서 25보다 오른쪽에 있는 값만 대상으로 생각하면 됩니다.

3 | 이제 [36, 49, 64, 81] 리스트에서 중간 위치를 찾습니다. 이 경우 49와 64의 한가운데가 중간 위치가 되는데, 두 자료 중 앞에 있는 값인 49를 중간 위치 값으로 뽑습니다.

4 | 찾는 값 36과 중간 위치 값 49를 비교합니다. 36 < 49이므로 찾는 값 36은 처음에 비교한 값인 25보다는 오른쪽에 있고 49보다는 왼쪽에 있습니다.

5 | ‘25보다 오른쪽에 있고 49보다 왼쪽에 있는 값’은 한 개뿐이므로 위치 번호 5의 36이 중간 위치 값입니다.

6 | 찾는 값 36이 중간 위치 값과 같으므로 위치 번호 5를 결괏값으로 돌려주고 종료합니다.

 

그림 12-3 이분 탐색으로 36을 찾는 과정