읽고 나면 진짜 쉬워지는 자료 구조 - 2. 이진 탐색
정렬된 리스트에서 특정 값을 빠르게 찾는 알고리즘
🔖 선형 스캔
선형 스캔이란? 그리고 장단점
리스트의 처음부터 끝까지 한 번에 하나씩 요소를 비교하여 목표값을 찾는 방법이다.
구현이 간단하고, 배열이 정렬되어 있지 않아도 사용할 수 있다는 장점이 있다.
다만, 배열의 크기가 크면 효율성이 떨어질 수 있으므로 이때는 다른 방법(이진탐색 등)을 고려하면 좋을듯
책에서도 '무식한 검사' 라고 표현한다.
JS로 구현하기
function linearSearch(arr, target) {
for (let i = 0; i < arrr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}시간 복잡도
Best: 목표값이 배열의 첫 번째에 있는 경우, 한 번만 비교하면 되므로 O(1)
Worst: 목표값이 배열의 마지막에 있거나 배열에 없는 경우, 모든 요소를 비교해야 하므로 O(N)
🔖 이진 탐색 알고리즘
이진 탐색이란?
'정렬된' 리스트에서 목표값을 찾는 알고리즘이다. 리스트를 반으로 분할하고, 목표값이 어느 쪽 절반에 속하는지 결정한다. 이후 목표값이 포함되지 않는 절반을 버리고, 여전히 목표값이 있을 수 있는 나머지 절반만 가지고 다시 같은 과정을 반복한다. 최종적으로는 마지막 값만 남을 때까지 이를 반복한다.
이진 탐색의 경우, 배열이 오름차순으로 정렬되어 있음을 이용한다.
이진 탐색 수행 전 배열을 정렬해야 하는 이유
앞서 말했듯, 이진 탐색은 정렬된 배열에서만 올바르게 동작하는 알고리즘이다. 배열이 정렬되어 있지 않다면, 이진 탐색을 수행해도 올바른 결과를 보장할 수 없다.
JavaScript에 내장된
sort()를 사용해 배열을 쉽게 정리할 수 있다.
JS로 구현하기
function binarySearch(arr, target) {
arr.sort((a, b) => (a - b));
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // 목표값 찾음
} else if (arr[mid] < target) {
left = mid + 1; // 오른쪽 절반 탐색
} else {
right = mid - 1; // 왼쪽 절반 탐색
}
}
return -1;
}시간 복잡도
sort함수: 일반적으로 O(N log N)이진 탐색: O(N log N)
전체: 배열 정렬과 이진 탐색을 하면 O(N log N)
🔖 선형 탐색 vs. 이진 탐색
시간 복잡도 측면
선형 스캔의 최악의 경우, 실행 시간은 데이터 크기에 '선형적으로' 비례한다.
이진 탐색은 최악의 경우라도 단계마다 데이터의 절반을 제거하기에 비교 횟수는 데이터 집합의 크기에 대해 로그적(logarithmic)이다. (e.g. N = 16일 때 최대 4번의 비교 필요 log₂16 = 4)
충분히 큰 리스트에 대해 원소 갯수의 로그만큼만 비교하면 된다는 이점이, 단계마다 드는 비용을 상쇄시킨다. 즉, 최악의 경우에도 데이터 크기가 증가함에 따라 (선형적에 비해) 실행 시간이 느리게 증가하여 여전히 효율적이다.
Last updated