선형 탐색 (linear search)

  • 순차적으로 모든 요소를 탐색하여 원하는 값을 찾아냄
  • 리스트 길이에 비례해 소요 시간이 늘어남
  • 복잡도 : O(n)

이진 탐색 (binary search) 

  • 탐색하려는 리스트가 이미 정렬돼 있을 때에만 적용 가능
  • 크기 순으로 정렬돼 있다는 성질 이용
  • 한 번 비교할 때마다 검사해야 할 리스트 길이를 반씩 줄임 (divide & conquer)
  • 알고리즘 복잡도 : O(log n)
  • 관련 문제