references
이번 글은 다음 자료들을 참고하여 작성하였습니다.
Binary search on Khan Academy
Implementing binary search of an array on Khan Academy
Running time of binary search on Khan Academy
What is an algorithm and why should you care?
우리는 살아가면서 수많은 문제를 맞닥뜨린다. 저녁 메뉴 고르기 같은 간단한 문제부터 부동산 계약이나 기업의 운명을 결정 짓는 중차대한 의사결정에 이르기까지 인생은 그야말로 문제해결의 연속이라고 볼 수 있다. algorithm이란 이러한 문제를 해결하기 위한 절차들의 집합이다. computer programming에서는 주로 문제 해결을 위한 명령어들의 집합을 뜻한다.
그렇다면 어떤 algorithm이 훌륭한 algorithm일까. 바로 정확성(correctness)와 효율성(efficiency)를 모두 잡는 algorithm이다. 아래 이어질 내용이 바로 배열 내 특정한 값을 탐색하는 데 정확하고 효율적인 Binary Search이다.
이진 탐색(Binary Search)
이진 탐색은 정렬된 배열에서 하나의 값을 찾아내는 데 효율적인 알고리즘이다. 주어진 배열을 절반씩 잘라나가며 목표값이 포함된 배열만을 추려내는 식으로 하나의 값이 남을 때까지 배열을 좁혀가는 작업을 반복하는 배열 탐색 방법이다.
Describing binary search
이진 탐색의 주된 개념은 값이 포함된 범위를 계속해서 추적해가는 것이다. 상대방이 정해놓은 1에서 100 사이의 숫자 하나를 맞힌다고 해보자. 답으로 25를 말하니 상대방이 그것보다는 높다 했고 다시 81이라고 말하자 그보다는 낮다고 했다. 그렇다면 정답은 26에서 80 사이에 있는 숫자일 것이다.
26에서 80 사이의 숫자가 정답이라고 했을 때 이 영역의 중간값은 53(즉, (26 + 80) / 2)일 것이다. 53도 정답보다 높다면 53부터 80까지숫자를 아래 그림처럼 제거 가능할 것이다.
Implementing binary search of an array
const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];`위 배열은 1부터 100까지 숫자 중 소수만을 모아놓은 것이다. 여기서 67이 몇 번째 놓였는지 맞히는 놀이라고 가정하자. 위 배열의 index number는 [0]부터 [24]까지이므로 변수를 minIdx = 0 , maxIdx = 24와 같이 설정할 수 있다.
첫 추측값으로 12번째((min + max) / 2)라고 대답한다면 12번째 값은 41이므로 틀린 답이다. 우리가 찾으려는 값의 index는 12보다 높으므로 정답은 index 12기준 배열의 오른쪽에 존재한다. 따라서 minIdx을 12 + 1로 갱신하고 maxIdx는 그대로 24로 둔다.
다음 중간값은 무엇일까? 13에서 24 사이에 정답이 포함돼 있으므로 중간값은 18(Math.floor(minIdx + maxIdx) / 2)이 된다. 따라서 primes[18] = 67이므로 2번 만에 정답을 찾게 되는 것이다.
Running time of binary search
배열에서 숫자를 탐색할 때 최대 탐색 횟수는 어떻게 알아낼까? 만약 array.length = 8인 배열에서 숫자를 찾을 때의 탐색 작업은 다음과 같을 것이다.
| 탐색 횟수 | 배열 길이 |
|---|---|
| 1 | 8 → 4 |
| 2 | 4 → 2 |
| 3 | 2 → 1 |
| 4 | 1 |
최종 길이가 1이 될 경우 정답을 포함하고 있을 것이므로 총 4번 작업을 수행한다.
그렇다면 배열의 길이가 16으로 8에 비해 2배 늘어난다면 어떨까? 마찬가지로 탐색 한 번마다 배열이 반씩 줄어들어 총 탐색 횟수는 5번이 될 것이다. 일정한 규칙을 발견했을 텐데, 배열의 길이가 2배 늘어날 때마다 작업 횟수는 1번 증가하게 된다.
즉 배열의 길이 n일 때부터 탐색 작업을 시작하여 배열의 길이가 1이 될 때까지 걸린 작업 횟수를 수학식으로는 log2n과 같이 나타낼 수 있다.
| n | log2n |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 4 | 2 |
| 8 | 3 |
| 16 | 4 |
| 32 | 5 |
| 64 | 6 |
| 128 | 7 |
| 256 | 8 |
| 512 | 9 |
| 1024 | 10 |
| 1,048,576 | 20 |
| 2,097,152 | 21 |
만약 n이 128이라면 작업 횟수는 8이 된다.
n이 2의 거듭제곱이 아닐 경우는 어떻게 계산할까? n을 1,000이라고 가정했을 때 1,000의 절반과 가장 가까운 2의 제곱수는 512(2의 9승)이다. 즉 필요한 작업 횟수는 10이라는 것이다. 실제로 1,000을 log 계산해보면 9.97이 나오고 여기에 1을 더하면 10.97이 된다. 정수값을 반환하기 위해 소수점을 버리면 길이 1000짜리 배열을 탐색하는 데 필요한 작업 횟수는 10이 나온다.
the entire code of binary search
function doSearch(array, target) {
let minIdx = 0;
let maxIdx = array.length - 1;
while (minIdx <= maxIdx) {
const midIdx = Math.floor((maxIdx + minIdx) / 2);
if (array[midIdx] === targetValue) {
return midIdx;
}
if (array[midIdx] < targetValue) {
minIdx = midIdx + 1;
} else {
maxIdx = midIdx - 1;
}
}
return -1;
}
const primes = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97,
];
console.log(doSearch(primes, 67));// 18
console.log(doSearch(primes, 50));// -1이진 탐색 절차
minIdx = 0,maxIdx = array.length - 1으로 설정- 만약
maxIdx < minIdx이라면 코드 실행 정지 target이array내에 없다면return -1midIdx을Math.floor(minIdx + maxIdx) / 2로 설정- 만약
arr[midIdx] === target이라면return midIdx - 만약
array[midIdx] < target이라면minIdx = midIdx + 1 - 만약
array[midIdx] > target이라면maxIdx = midIdx - 1 - 조건을 충족할 때까지 2~7과정 반복.
