이진 탐색 (Binary Search) - JavaScript
Algorithm
2024년 1월 22일
정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
예시
찾고자 하는 값 : 4- 시작점: 0, 끝점: 9, 중간점: 4
- 중간점이 두개일 경우 소수점이하 제거 (0+9) / 2 = 4.5 ⇒ 4
- 찾고자하는 값 4가 중간점인 8보다 작음 ⇒ 중간점 포함 오른쪽 제거
- 시작점: 0, 끝점: 3, 중간점: 2
- 이번에는 찾고자 하는 값 4가 중간점인 2보다 큼 ⇒ 중간점 포함 왼쪽 제거
-
시작점: 2, 끝점: 3, 중간점: 2
- 찾고자하는 값과 중간 점이 같음 ⇒ 탐색 종료
🕰️ 시간복잡도
-
단계 마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log_2_N에 비례 (로그 이의 엔 입니다.)
ex) 초기 데이터 개수 : 32개 → 16개 →8개 → 4개 ….
-
이렇게 탐색 범위를 절반씩 줄이므로 시간 복잡도는 O(logN)
🛠 구현
const binarySearch = (list, target, left, right) => {
let mid = 0;
while (left <= right) {
// 가운데 인덱스
mid = Math.floor((left + right) / 2);
if (list[mid] === target) {
return mid;
}
// 대소 비교로 범위 지정
if (list[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
const sample = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
// 정렬되어 있는 배열에서하는게 이진탐색이니까..!
sample.sort((a, b) => a - b);
// ( 찾을 배열, 탐색할 값, 시작점, 끝점 )
const result = binarySearch(sample, 7, 0, sample.length - 1);
console.log(result);