이진탐색

순차 탐색 vs 이진 탐색

ex) 리스트에서 12인 원소의 위치 찾기

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인 → 시간복잡도: O(N)

순차탐색 예시

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색 → 시간복잡도: O(logN)

이진탐색 예시

• 이진탐색 수행할 때 시작점(left)와 끝점(end)을 기준으로 탐색 범위 명시
• 각 단계마다 탐색 범위를 2로 나누기
• 이상적인 경우 매 단계마다 범위가 반으로 감소 → log 복잡도를 가짐
• 대표적인 사례
  • 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
  • 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

이진 탐색 코드

이진 탐색은 배열이 정렬되어있다는 가정하에 수행

1. 재귀함수 이용

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); // 중간 인덱스 값보다 target 값이 작은 경우 왼쪽 탐색
    else return binarySearch(arr, target, mid + 1, end); // 중간 인덱스 값보다 target 값이 더 큰 경우 오른쪽 탐색
}

2. 반복문 이용

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; // 중간 인덱스 값보다 target 값이 작은 경우 왼쪽 탐색
        else start = mid + 1; // 중간 인덱스 값보다 target 값이 더 큰 경우 오른쪽 탐색
    }
    return -1; // 값을 찾지 못한 경우 -1 리턴
}

 

 

정렬된 배열에서 특정 원소 개수 구하기

코딩 테스트에서 정렬된 배열에서 특정 범위에 해당하는 원소의 개수를 계산하는 문제 종종 존재

→ lowerBound() 함수와 upperBound() 함수 사용

lowerBound(arr, x)

정렬된 순서를 유지하면서 배열 arr에 x를 넣은 가장 왼쪽 인덱스 반환

function lowerBound(arr, target, start, end) {
    while (start < end) {
        const mid = parseInt((start + end) / 2);
        if (arr[mid] >= target)
            end = mid; // 최대한 왼쪽으로 이동
        else start = mid + 1;
    }
    return end;
}

upperBound(arr, x)

정렬된 순서를 유지하면서 배열 arr에 x를 넣은 가장 오른쪽 인덱스 반환

function upperBound(arr, target, start, end) {
    while (start < end) {
        const mid = parseInt((start + end) / 2);
        if (arr[mid] > target) end = mid;
        else start = mid + 1; // 최대한 오른쪽으로 이동
    }
    return end;
}

 

countByRange()

정렬된 배열에서 값이 특정 범위에 속하는 원소의 개수 계산

function countByRange(arr, leftValue, rightValue) {
    let rightIndex = upperBound(arr, rightValue, 0, arr.length);
    let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
    return rightIndex - leftIndex;
}
// 배열 선언
let arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9];
// 값이 4인 데이터 개수 출력
console.log(countByRange(arr, 4, 4));
// 값이 [-1, 3] 범위에 있는 데이터 개수 출력
console.log(countByRange(arr, -1, 3));

 

 

 

파트메트릭 서치

이진 탐색 조건: 변경할(최적화할) 값 x에 대해 f(x)가 단조 증가 혹은 단조 감소

- 단조 증가 함수: x ≦ y 이면 f(x) ≦ f(y)인 경우 → 계단 형식 혹은 왼쪽보다 오른쪽 값이 더 큼

접근 방법

최적화 문제를 결정 문제(예/아니오)로 바꾸어 해결하는 방법

ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

- 파라메트릭 서치 문제는 이진 탐색 이용해서 해결 가능