사전 ADT

탐색 가능한 형태의 (key, element)쌍 항목의 모음
무순사전과 순서사전으로 분류

메소드

• integer size()
• boolean isEmpty()
• element findElement(k)
• insertItem(k, e)
• element removeElement(K)

키의 종류

• 유일키 : 한 개의 키에 하나의 데이터
• 중복키 : 한 개의 키에 여러 개의 데이터

무순사전의 선형탐색

선형탐색은 O(n)

Alg findElement(k) 
  input 리스트 L, 키 k
  output 키 k에 해당하는 원소
1. L.initialize(i)
2. while(L.isValid(i))
     if(L.key(i) = k)
       return L.element(i)
     else
       L.advance(i)
3. return NoSuchKey

순서사전의 선형탐색과 이진탐색

• 선형 탐색
  O(n)

Alg findElement(k)
  input 리스트 L, 키 k
  output 키 k에 해당하는 원소
1. L.initialize(i)
2. while(L.isValid(i))
     if(L.key(i) = k)
       return L.element(i)
     elseif(L.key(i) > k)
       return NoSuchKey
     else
       L.advance
3. return NoSuchKey

• 이진 탐색
  배열로 구현된 경우 O(logn), 연결리스트이면 O(n)

Alg findElement(k)
  input 정렬된 배열 A[0..n-1], 키 k
  output 키 k에 해당하는 원소
1. return rFindElement(k, 0, n-1)

Alg rFindElement(k, l, r)
  input 키 k, 인덱스 l r
  output 키 k에 해당하는 원소
1. if(l>r)
     return
2. mid ← (l+r)/2
3. if(k = A[mid])
     return element(A[mid])
   elseif(k < A[mid])
     return rFindElement(k, l, mid-1)
   else
     return rFindElement(k, mid+1, r)