Sequential Search vs Binary Search ( 순차 탐색 vs 이진 탐색)

순차 탐색(sequential search) 혹은 선형 탐색(linear search)라고도 하는 탐색에 대해 알아봅시다.

 

순차 탐색은 말 그대로 앞에서부터 순차적으로 데이터를 찾는 탐색 방법입니다. 

 

코드)

#include <iostream>
#include <vector>

int SequentialSearch(std::vector<int> v, int target) {
  int N = v.size();
  for (int i = 0; i < N; i++) {
    if (v[i] == target) return i;  // 찾으면 그 인덱스를 반환
  }
  return -1;  // 찾지 못한 경우 -1 반환
}

int main(void) {
  std::vector<int> v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  std::cout << "SequentialSearch : " << SequentialSearch(v1, 7) << '\n';
  return 0;
}

 

이렇게, 앞에서부터 하나씩 찾아야 하는 값과 비교하며 나아갑니다.

찾는 값을 찾은 경우, 바로 그 위치를 반환합니다.

 

 

 

이번에는, 이진 탐색에 대해 알아보겠습니다.

이진 탐색이란, 데이터를 두 조각으로 나누어서 탐색하는 것입니다. 

그림으로 한번 보시죠. 

 

어떤가요? 그림으로 보니 잘 이해가 됩니다.

 

그럼 코드도 한번 살펴보죠.

 

 

코드)

#include <iostream>
#include <vector>

int BinarySearch(std::vector<int> v, int low, int high, int target) {
  while (low <= high) {
    int N = v.size();
    int mid = (low + high) / 2;

    if (v[mid] == target)
      return mid;
    else if (v[mid] < target)
      low = mid + 1;
    else if (v[mid] > target)
      high = mid - 1;
  }
  return -1;  // 찾지 못한 경우 -1 반환
}

int main(void) {
  std::vector<int> v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  std::cout << "BinarySearch : " << BinarySearch(v1, 0, 9, 7) << '\n';
  return 0;
}

 

 

이진 탐색은 데이터의 크기가 클 때 유용할 것 같습니다.

 

 

그럼 이제 순차 탐색과 이진 탐색의 시간을 비교해보겠습니다.

 

 

순차 탐색의 시간 복잡도)

최선의 경우 : 데이터의 처음 값이 찾고자하는 값일 때 바로 찾을 수 있습니다 -> O(1)

 

최악의 경우 : 데이터의 마지막 값이 찾고자하는 값일 때는, 끝까지 찾아봐야 합니다.

                     데이터의 크기가 n이라고 할 때 -> O(n)

 

이진 탐색의 시간 복잡도)

최선의 경우 : mid인덱스 값이 찾고자하는 값일 경우, 바로 찾을 수 있습니다 ->O(1)

 

최악의 경우 : 찾고자하는 값이 처음이나 마지막에 있는 경우, 하나만 남을 때까지 계속 탐색해야 합니다.

 

시간 복잡도 비교)

 

두 탐색의 시간 복잡도 그래프를 간단하게 그려본 것입니다.

 

데이터의 크기가 작을 때는 순차 탐색이 유리한 경우도 있지만,

데이터의 크기가 커지면서 이진 탐색의 시간이 상대적으로 빨라지는 것을 확인할 수 있습니다.