[자료구조] 탐색 (순차 탐색, 이원 탐색, 두 리스트 비교)

탐색

• 리스트: 하나 이상의 필드로 된 레코드의 집합
• 키(key): 레코드를 구분하기 위해서 사용되는 필드

 

순차 탐색

template <class E, class K>
int SeqSearch(E *a, const int n, const K &k)
{   // a[1:n]을 왼쪽에서 오른쪽으로 탐색
    // a[i]의 키 값이 k와 같은 가장 작은 i를 반환, 없으면 0 반환
    int i;
    for (i = 1; i <= n && a[i] ! = k; i + +);
    if (i > n) return 0; // i값을 찾지 못한 경우
    return i;            // i값을 찾은 경우
}

 

시간복잡도 - O(n)

 

순차 탐색의 성능 향상(정렬된 리스트의 경우)

• SepSearch의 for 조건 부분을 i <= n && a[i] < k로 변경
• if 조건 i > n을 i > n || a[i] != k로 변경
• 탐색이 실패할 때 성능 향상

 

 

이원 탐색(Binary Search)

int BinarySearch(int *a, const int x, const int left, const int right)
{ // 배열 a에서 x값 탐색
    if (left <= right)
    {
        int middle = (left + right) / 2;
        if (x < a[middle])
            return BinarySearch(a, x, left, middle - 1);
        else if (x > a[middle])
            return BinarySearch(a, x, middle + 1, right);
        return middle;
    }
    return -1; // 배열에 x값 존재하지 않음
}

 

시간복잡도 - O(log n)

 

 

두 개의 리스트 비교

비 정렬 리스트의 경우

void Verify1(Element *l1, Element *l2, const int n, const int m)
{ // 길이가 n, m인 두 리스트 l1, l2를 비교
    bool *marked = new bool[m + 1];
    fill(marked + 1, marked + m + 1, false);

    for (i = 1; i <= n; i++)
    {
        int j = SeqSearch(l2, m, l1[i]);
        if (j == 0)
            cout << l1[i] << " not in l2 " << endl; // (1)을 만족
        else
        {
            if (!Compare(l1[i], l2[j])) // (3)을 만족
                cout << "Discrepancy in " << l1[i] << endl;
            marked[j] = true; // l2[j]를 겁사한 것으로 표시
        }
    }
    for (i = 1; i <= m; i++)
        if (!marked[i])
            cout << l2[i] << " not in l1. " << endl; // satisfies (2)
    delete[] marked;
}

 

시간복잡도 - O(nm)

 

• (1) l1리스트에 있는 키와 대응되는 레코드가 l2리스트에 없으면 메시지를 출력
• (2) (1)과 반대인 경우 메시지 출력
• (3) 같은 키를 가진 두 레코드 사이에 차이가 없으면, 결과에 대해 메시지 출력

 

정렬 리스트의 경우

void Verify2(Element *l1, Element *l2, const int n, const int m)
{ // l1과 l2 정렬 + Verify1과 같은 기능
    Sort(l1, n); // 키를 오름차순 정렬
    Sort(l2, m);
    int i = 1, j = 1; // l1, l2에서 작업할 위치
    while ((i <= n) && (j <= m))
        if (l[i] < l[j])
        {
            cout << l1[i] << " not in l2" << endl;
            i++;
        }
        else if (l[i] > l[j])
        {
            cout << l2[j] << " not in l1" << endl;
            j++;
        }
        else
        { // 같은 키들
            if (!Compare(l1[i], l2[j]))
                cout << "Discrepancy in " << l1[i] << endl;
            i++;
            j++;
        }
    if (i <= n)
        OutputRest(l1, i, n, 1); // l1의 레코드 i부터 n까지 출력
    else if (j <= m)
        OutputRest(l2, j, m, 2); // l2의 레코드 j부터 m까지 출력
}

 

시간복잡도 - O(\(t_{sort}(n) + t_{sort}(m) + n + m\)

\(t_{sort}(n)\): n개의 레코드를 가진 리스트를 정렬하는데 걸리는 시간 - O(n log n)시간에 정렬 가능