8. Search Algorithm

Search algorithms

Items이 주어지고 원하는 item을 찾고 싶을 때 사용하는 알고리즘입니다.

 

Sequential search

처음부터 하나하나 비교해가며 아이템을 찾는 방법입니다.

Sequential search

가장 기초적인 알고리즘입니다.

• Best case
  $O(1)$
• Worst case
  $O(n)$
• Average case
  $O({n \over 2}) = O(n)$

 

Binary search

정렬된 items에 대해서 middle point부터 찾는 알고리즘입니다. Mid와 찾는 item의 대소 관계를 이용해 원하는 item을 찾습니다.

Binary search

Alternative implementation

• Best case
  $O(1)$
• Worst case
  $O(log n)$
• Average case
  $O(log n)$

 

Interpolation search

Interpolation search

• Best case
  $O(1)$
• Worst case
  $O(n)$
  [1,2,3,4,5,6,7,8,9,100]이고 target이 10인 경우 전부다 비교하게 된다.
• Average case
  $O(log (logn))$
  증명

 

Exponential search

Exponential search

• Best case
  $O(1)$
• Worst case
  $O(log i)$ 
  i : element가 위치하는 index
• Average case
  $O(log i)$