[자료구조] Sequential Search 순차탐색

순차탐색

• 용어정리 리스트 list : 하나 이상의 필드로 된 레코드의 집합 ex) 전화부 키 Key : 레코드를 구분 (대표) 하기 위해 사용되는 필드 ex) 레코드가 이름, 전화번호, 주소 라면 키는 찾고자 하는 정보
  

• 순차 탐색 Sequential Search 레코드 리스트를 왼편에서 오른편 또는 오른편에서 왼편으로 레코드를 검사
  

template<class E, class K>
int SeqSearch(E *a, const int n, const K& k){ // a는 레코드, n은 갯수, k를 찾아봐라
    int i;
    for (i = 1; i<=n&&a[i] != k; i++); // 1부터 쭉 가면서 k가 나올 때 까지 찾는다
    if (i>n) return 0; // 없으면 0 리턴
    return i; // 아니면 키가 몇번째인지 리턴한다.
}

• 키가 어디에 있는지 알 수 없다 → 키를 찾으려면 평균 (n+1) / 2
• n개의 레코드를 가진 리스트 탐색 시간 : O(n)

Ordered List의 탐색

이 리스트에 순서가 있으면 어떻게 되냐? → 다 찾을 필요 없이 순서에 맞게 되어 있으니 조건을 넣어줄 수 있다

• SeqSearch 코드를 ordered list의 경우에 맞게 수정

  • for 조건 부분을 i ≤ n && a[i] && a[i] < k 로 변경
    i번째 값이 k보다 크면 찾을 필요가 없다

  • 조건 i>n 을 i >n || a[i] ! = k 로 함께 변경

    ⇒ search 하는 속도가 빨라진다

• 이원탐색 Binary Search : 1장
  • n개의 레코드를 가진 리스트를 탐색하기 위해 O(log n)시간이 걸림.
    (순차 탐색보다 빠름)
• 순차나 이원 탐색 방법은 실제로 사람이 사용하는 탐색방법과 대응되지 않음

이진탐색 : 정렬된 경우의 탐색

template<class E, class K>
int BinarySearch(E *a, const int n, const K& k){
    int i; int left = 1, right = n, mid; // left, right를 각각 1과 n으로 잡고
    
    while(left<=right){ // 찾을 때 까지 돈다 
        mid = (left + right)/2; // mid는 가운데값이라고 정하자
        
        if(k<a[mid])  // k가 중간값보다 작으면
            right = mid - 1; // 중간보다 왼쪽에 있으니까 RIGHT를 중간값보다 작게
        
        else if(k>a[mid]) // K가 중간값보다 크면
            left = mid + 1; // 오른쪽에 있으니까 left를 중간값보다
        
        else return mid; // 둘 다 아니면 값을 찾은 것! 
    }
    return 0; // 못찾으면 
}

⇒ 반씩 잘라서 1개가 나올 때 까지 몇 번 잘라야 하나 → $log_2n$ 번

• 정렬된 n개의 레코드를 가진 리스트 탐색시간 : O(log n)

정렬의 필요성

• 정렬의 두 가지 중요한 사용법
  1. 탐색에서 보조로 사용
  2. 리스트의 엔트리를 비교하는 방법으로 사용
• 정렬 방법

  1. 내부 방법 internal methods → 알고리즘이 더 중요

     정렬할 리스트가 작아서 전체적인 정렬이 메인 메모리 상에서 실행될 수 있을 때 사용

  2. 외부 방법 external methods → 데이터베이스에서 많이 사용함

     Main Memory 크기를 넘는 큰 리스트를 정렬하는데 사용