안녕하세요! MightyCoder입니다. 2021년 첫 포스트네요!(사실 이전 포스트도 몇개 없었지만 앞으로 더 열심히 블로그를 운영할 계획입니다..ㅎㅎ)
이번 포스트에서는 Javascript를 이용한 이진 탐색(Binary Search)을 소개하려고 합니다.
1. 알고리즘 설명
이진 탐색은 탐색할 범위를 축소해가며 원하는 값을 찾는 탐색 알고리즘입니다. 모든 탐색 범위를 전부 탐색하는 선형 탐색(Linear Search)보다 속도 면에서 빠르다는 장점이 있습니다. 그렇다면 어떠한 방식으로 탐색 범위를 축소하는 걸까요?
이진 탐색을 설명하기 위해 먼저 10개의 정수를 포함하고 있는 배열 arr를 선언하겠습니다.
let arr = [1,4,6,2,10,3,5,8,9,7];
이제 위의 배열에서 8을 찾아보겠습니다. 아 그전에 이진 탐색에서 가장 중요한 부분! 이진 탐색은 정렬된 배열에 대해서만 수행이 가능합니다. 하지만 arr 배열은 현재 정렬되지 않은 상태입니다. 그렇다면 먼저 오름차순 정렬을 수행하겠습니다.
arr.sort(function() {
return a - b;
})Javascript의 빌트인 함수인 sort를 이용해 오름차순 정렬을 수행했습니다. (sort 함수에 대한 자세한 설명은 이곳을 참고해주세요) 이분 탐색은 두 개의 포인터를 사용합니다. 보통 이 포인터들을 left, right로 네이밍하여 사용하는데 이름 그대로 왼쪽 부분에 존재하는 포인터와 오른쪽 부분에 있는 포인터를 가르킵니다. 그리고 이 포인터들의 위치하는 배열의 인덱스값을 사용해 배열의 중앙 인덱스값을 구합니다. 그럼 구현해보겠습니다.
//이분 탐색 함수 생성
function binarySearch(targetValue, arr) {
let left = 0;
let right = arr.length - 1;
let mid = Math.floor((left + right) / 2);
}left를 배열의 첫 인덱스 그리고 right를 마지막 인덱스로 초기화해줍니다. 그런 후 해당 인덱스값을 이용하여 중간 인덱스값인 mid를 구해줍니다. 이제 찾으려는 값과 배열의 중간 인덱스값을 비교하고 같을 경우 찾으려는 값을 반환하고 탐색을 종료합니다.
//찾으려는 값과 배열의 중간값이 같을 경우 탐색 종료
if(targetValue === arr[mid]){
return targetValue;
}한번에 원하는 값을 찾는 경우는 정말 좋은 경우이지만 흔히 볼 수 있지는 않습니다. 찾고자 하는 값이 중간값이 아닐 경우가 더 많겠죠? 이 경우 이진 탐색은 이제 mid를 찾고자 하는 값과 비교합니다. 만약 mid가 찾고자 하는 값보다 작을 경우 left의 값을 mid보다 1만큼 증가시키고 반대의 경우는 right의 인덱스값을 mid보다 1만큼 작게 하락 시켜 탐색 범위를 줄입니다. 그림으로 다시 한번 8을 찾는 과정을 알아보겠습니다.
left는 현재 0번 인덱스에 자리하고 있고 right는 9번 인덱스에 있습니다. left와 right의 값을 가지고 mid를 구하면 5가 나옵니다.(반올림을 하느냐 안하느냐에 따라 6이 나올수도 있습니다) 일단 위의 경우는 mid가 5번 인덱스를 가르키고 있습니다.
배열의 5번째 인덱스에는 6이라는 값이 저장되어 있습니다. 우리가 찾는 값인 8은 아니고 8보다 작은 값입니다. 원하는 값보다 작으니 left 인덱스의 위치를 변경해줍니다. 새로운 left의 위치는 mid + 1이므로 6이 됩니다.
left의 값이 6으로 변경되었으니 새로운 mid의 값을 구해줍니다. Math.floor(left + right)를 해주면 7이 나오죠. 이제 배열의 7번 인덱스 값과 우리가 찾는 값을 비교해봅시다. 8과 8로 동일합니다. 그럼 원하는 값을 찾았으니 8을 반환해주고 함수를 종료하면 됩니다.
2. 구현
앞선 설명을 통해 이진 탐색을 살펴보았습니다. 이제부터는 실제로 Javascript를 이용해 구현해보도록 하겠습니다. 이진 탐색의 소스코드는 다음과 같습니다.
function binarySearch(array, targetValue) {
let left = 0;
let right = array.length - 1;
while(left <= right) {
let mid = Math.floor((left + right) / 2);
if(array[mid] === targetValue) {
return array[mid];
}
else if(array[mid] > targetValue) {
right = mid - 1;
}
else if(array[mid] < targetValue) {
left = mid + 1;
}
}
return -1;
}소스 코드에 대해 설명하겠습니다. binarySearch 함수는 매개변수로 탐색을 수행할 array와 탐색을 원하는 숫자인 targetValue를 받습니다. 함수 내부에서는 먼저 left와 right를 각각 배열의 0번째, 마지막 인덱스로 초기화해줍니다. 그 뒤에 while 문을 사용하여 left가 right보다 작거나 같을 동안 탐색을 수행합니다. while 문 안에서는 mid의 값을 구해주고 조건문을 통해 mid에 해당하는 인덱스의 요소가 탐색하고 있는 값과 같은지 비교합니다. 조건들은 다음과 같습니다.
- 같을 경우 → 탐색을 원하는 값을 반환하고 탐색을 종료합니다.
- mid 인덱스의 요소 > 탐색하는 값 → right의 값을 미드보다 1작은 값으로 설정(right = mid - 1)
- mid 인덱스의 요소 < 탐색하는 값 → left의 값을 미드보다 1 큰 값으로 설정(left = mid + 1)
만약 while 문이 끝날 때까지 원하는 값을 찾지 못한다면 while 문을 빠져나오고 -1을 반환하고 탐색을 종료합니다.
3. 시간복잡도
이진 탐색의 시간복잡도는 다음과 같습니다.
- 최선: O(1)
- 평균: O(log N)
- 최악: O(log N)
최선의 경우는 첫 루프에서 원하는 값을 찾은 경우입니다. 이럴 경우 O(1)의 시간복잡도를 가지게 됩니다. 그 외의 경우에는 탐색할 범위가 대략 절반씩 줄어들기때문에 O(log N)의 시간복잡도를 가집니다.
4. 정리
- 이진 탐색은 정렬된 배열에 대해서만 수행 가능하다.
- 탐색을 위해 배열의 인덱스를 저장하는 left, right 포인터로 범위를 지정하고 해당 포인터들을 이용해 중앙 인덱스 값인 mid를 구한다.
- mid에 해당하는 배열의 요소 값과 찾고자 하는 값을 비교한다.
- left가 right보다 작거나 같을 때까지 탐색 과정을 반복한다.
- left가 right보다 커질경우 탐색을 종료한다. 해당 경우는 원하는 값이 존재하지 않는 경우다.
- 시간복잡도는 최선의 경우 O(1), 평균 및 최악의 경우 O(log N)이다.
이상으로 Javascript를 이용한 이진 탐색 소개를 마치도록 하겠습니다. 본 포스트는 개인적으로 공부를 하며 정리한 내용이므로 잘못된 내용이 포함되어 있을 수 있습니다. 잘못된 내용을 파악하셨을 경우 피드백 주시면 정말 감사하며 적극 반영하겠습니다. 감사합니다.