[TypeScript] 자료 구조로 담아내기. #5 - 배열(with. 선형 탐색)

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

배열에서 원하는 요소의 위치를 찾아내기 위해서는 어떻게 해야 할까요? 이런 상황에서 사용하는 연산을 탐색이라고 합니다.

선형 탐색

선형 탐색은 가장 단순하게 탐색을 수행하는 방법입니다. 배열의 시작부터 끝까지 목표를 찾을 때까지 순차적으로 탐색을 수행합니다.

function linearSearch<T>(
    l: number,
    r: number,
    cmp: (i: number) => boolean
): number {
    for(let i = l; i <= r; i++) {
        if(!cmp(i)) { continue; }
        return i;
    }
    return -1;
}

l과 r로 지정된 범위를 순차적으로 순회하며 cmp를 호출합니다. cmp는 인덱스를 전달받고 해당 위치에 목표가 저장되어 있다면 true, 그렇지 않으면 false를 반환합니다. true를 반환하면linearSearch 함수는 즉시 현재 인덱스를 반환합니다. 탐색 실패 시 -1을 반환합니다.

적용

class BasicArrayImpl<T> implements BasicArray<T> {
    search(element: T): number {
        return linearSearch(
            0,
            this.slots.length - 1,
            i => this.slots[i] === element
        );
    }
}

작성한 함수는 위와 같이 간단히 적용할 수 있습니다.

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

묻고 답하기

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