순차 탐색 (Sequential Search) 알고리즘

Template <class T>
int SeqSearch (T* a, const int n, const T& k) {
// a[0] → a[n-1]까지 왼쪽에서 오른쪽으로 탐색
// k와 같은 키 값을 가진 a[i] 중 가장 작은 index 반환
// 미존재시 -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)