이진 탐색 알고리즘은 순차 탐색보다 훨씬 좋은 성능을 보이는 알고리즘 입니다. 이진 탐색 알고리즘을 적용하기 위해서는 다음과 같은 조건이 성립되어야 합니다.
" 배열안의 요소(데이터)들이 정렬되어 있어야 한다. "
해당 알고리즘은 정렬된 데이터가 아니면 적용이 불가능합니다. (정렬의 기준 및 방식과는 관계없습니다.) 때문에 이진 탐색 알고리즘보다 성능이 덜한 순차 탐색 알고리즘도 우리에겐 유용한 알고리즘 입니다.
예제를 보겠습니다. 우선 길이가 9인 배열에 다음과 같이 정렬된 상태로 데이터가 저장되어 있습니다. (배열의 이름은 arr)
해당 배열의 이진 탐색 알고리즘의 첫 번째 시도는 다음과 같습니다. 1. 배열 인덱스의 시작과 끝은 각각 0과 8입니다. 2. 0과 8을 합하여 그 결과를 2로 나눕니다. 3. 2로 나워서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인합니다.
다음 그림과 같이 중앙에 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘의 첫번째 시작입니다.
첫 시도를 통해 3의 값을 찾지 못했으니 두 번째 시도를 할 차례입니다. 두 번째 시도는 다음과 같습니다. 1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교합니다. 2. 대소의 비교결과는 arr[4] > 3 이므로 탐색의 범위를 인덱스 기준 0~3으로 제한합니다. 3. 0과 3을 더하여 그 결과를 2로 나눕니다. 이때 나머지는 버립니다. 4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인합니다.
* 이 두 번째 시도 과정에서 주의 깊게 살펴볼 것은 탐색의 대상을 반으로 줄였다는 사실입니다. 이는 어디까지나 배열에 데이터가 정렬된 상태로 저장되었기 때문에 가능한 일이며, 이것은 바로 이진 탐색 알고리즘의 핵심입니다.
이 내용을 그림으로 정리하면 다음과 같습니다.
세 번째 시도는 다음과 같습니다. 1. arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교합니다. 2. 대소의 비교결과는 arr[1]<3 이므로 탐색의 범위를 인덱스 기준 2~3으로 제한합니다. 3. 2와 3을 더하여 그 결과를 2로 나눕니다. (나머지 버리기) 4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인합니다.
이렇게 두 번째 시도 이후부터는 동일한 패턴을 반복합니다. 하지만 세 번째 탐색에서 탐색 대상인 3을 찾고 탐색은 마무리가 되죠. 3번째 시도 내용의 그림입니다.
3번의 탐색만에 탐색 대상을 찾게 되었습니다.
이렇게 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어내는 알고리즘입니다. (불필요한 탐색 작업을 덜어냅니다.)
