[TypeScript] 자료 구조로 담아내기. #6 - 배열(with. 이진 탐색)

이번 편은 이전 편으로부터 이어집니다.

선형 탐색은 소규모 시스템에서는 충분히 빠릅니다. 하지만 대규모 시스템에서는 충분치 않을 수 있습니다. 일반적으로 배열을 정렬된 상태로 유지하면 더 빠른 속도의 탐색 알고리즘을 선택할 수 있습니다.

이진 탐색

이진 탐색은 정렬된 배열에서 선택할 수 있는 대표적인 탐색 알고리즘입니다. 이진 탐색은 목표가 아닌 대상을 범위로 소거하여 탐색 범위를 매우 빠르게 좁혀 나갈 수 있습니다.

function binarySearch<T>(
    l: number,
    r: number,
    cmp: (i: number) => number
): number {
    if(r < l) { return -1; }

    const i = (l + r) >> 1;
    const res = cmp(i);
    if(res === 0) { return i; }
    return res < 0 ?
        binarySearch(l, i - 1, cmp) :
        binarySearch(i + 1, r, cmp);
}

이진 탐색은 대표적인 분할 정복 기반 알고리즘입니다. 중앙부터 탐색을 시작하여 목표가 현재 요소보다 선임자라면 현재 요소를 포함한 우측 요소를 모두 폐기하고, 좌측에 대해 탐색을 계속합니다. 후임자라면 반대입니다. 이 과정은 목표를 찾는 데 성공하거나 시작 인덱스와 끝 인덱스가 역전될 때까지 계속됩니다. 코드의 흐름은 아래와 같습니다.

1. 시작 인덱스가 끝 인덱스보다 크면 탐색을 종료하고 -1을 반환하여 탐색에 실패를 알립니다.

2. 현재 인덱스를 계산합니다. 이는 시작 인덱스와 끝 인덱스의 중앙입니다. 즉, 두 인덱스를 더하고 2로 나눈 몫을 취한 수치입니다.

3. cmp에 현재 인덱스를 전달합니다. cmp는 탐색 목표와 현재 요소의 관계를 수치로 반환합니다. 목표가 선임자라면 음수, 후임자라면 양수, 동등하다면 0을 반환합니다.

4. 동등하다면 탐색을 종료하고 현재 인덱스를 반환합니다.

5. 목표가 현재 요소보다 선임자라면 현재 위치의 좌측에서 탐색을 계속합니다. 즉, 끝 인덱스를 현재 인덱스보다 1 작도록 설정하여 순서 1로 돌아갑니다. 후임자라면 반대입니다. 즉, 시작 인덱스를 현재 인덱스보다 1 크도록 설정하여 순서 1로 돌아갑니다.

적용

class SortedArrayImpl<T> implements SortedArray<T> {
    constructor(private compare: (a: T, b: T) => number) {}

    search(element: T): number {
        return binarySearch(
            0,
            this.slots.length - 1,
            i => this.compare(element, this.slots[i])
        );
    }
}

생성자 매개변수를 통해 두 요소의 순서를 비교하는 compare 함수를 받습니다. 이후는 linearSearch와 유사하게 사용할 수 있습니다.

내용은 다음 편에서 이어집니다. 읽어주셔서 감사합니다!

묻고 답하기

개인적인 판단에 의해 적절하다고 여겨지는 경우, 모두가 볼 수 있도록 이곳에 문답이 추가됩니다. 그렇지 않더라도 질문에 대한 답변은 별도로 이루어집니다.