7. 탐색

1. 순차탐색  시간복잡도 : O(n)

특정 값을 순서대로 탐색하여 찾는 탐색 알고리즘.

Template <class T>
int SeqSearch(T*a, const int n, const T& k) 
// a[0:n-1]을 왼쪽에서 오른쪽으로 탐색한다. 
// a[i]의 키 값이 k 와 같은 가장 작은 i를 반환한다. 
// 그런 i가 없으면 -1을 반환한다 
{ 
   int i; 
   for (i=0; i<n && a[i]!= k; i++) ; 
   if (i >= n) return -1;
   return i; 
} 
프로그램 분석:
    최선의 경우: 1,  최악의 경우: n,  평균의 경우: (n+1)/2   
    시간복잡도: O(n) 

 

2. 이진 탐색  시간복잡도 : O(log n)

특정 값을 기준으로 두고 값을 찾는다. 중요한 점은 배열이 정렬되어 있어야 한다는 점이다.

template <class T> 
   int BinarySearch(T *a, const T& k, const int n)
   // 정렬된 배열 a[0], ..., a[n-1]에서 x를 탐색한다.
   {
       for (int left = 0, right = n-1; left <= right;){  // 원소가 더 있을 때까지
            int middle = (left + right) / 2;
           switch (comare(k, a[middle]) {
 	 	      case '>' : left = middle + 1; break;     // k > a[middle]
 		      case '<' : right = middle - 1; break;   // k < a[middle]
		      case '=' : return middle;                   // k == a[middle]
           }   // switch의 끝
       }        // for의 끝
     return -1; // 발견되지 않음
   }  // BinarySearch의 끝

분석: 최선의 경우: 1,  최악의 경우: log n 
            시간복잡도: O(log n)