이진탐색 이해하기
- 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다
- 시작점(left)와 끝점(right)을 기준으로 탐색 범위를 명시한다
- 각 단계마다 탐색 범위가 반으로 감소하므로, 로그(log) 복잡도를 가진다
- 순차 탐색(리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인)은 O(N) 시간복잡도를 가진다
대표적인 사례
- 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
- 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우
이진 탐색 코드 예시
재귀 함수
function binarySearch(arr, target, start, end) {
if (start > end) return -1;
let mid = parseInt((start + end) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
else return binarySearch(arr, target, mid + 1, end);
}
// N = 원소의 개수, target = 찾고자 하는 값
let N = 10;
let target = 7;
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const result = binarySearch(arr, target, 0, N - 1);
result === -1
? console.log("원소가 존재하지 않습니다.")
: console.log(`${result + 1}번째 원소입니다.`);반복문
function binarySearch(arr, target, start, end) {
while (start <= end) {
let mid = parseInt((start + end) / 2);
if (arr[mid] === target) return mid;
else if (arr[mid] > target) end = mid = 1;
else start = mid + 1;
}
return -1;
}
// N = 원소의 개수, target = 찾고자 하는 값
let N = 10;
let target = 7;
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const result = binarySearch(arr, target, 0, N - 1);
result === -1
? console.log("원소가 존재하지 않습니다.")
: console.log(`${result + 1}번째 원소입니다.`);