SequentialSearch (순차 탐색)

순차 탐색이란, 배열이 주어졌을 때, 앞에서부터 순차적으로 찾는 탐색입니다.

 

이런 배열이 주어졌을 때, 9를 찾으려면 어떻게 해야할까요?

 

우리가 눈으로 보기에 그냥 바로 9가 보이겠지만 컴퓨터는 그렇게 할 수 없습니다.

 

배열의 크기가 100만개, 1000만개 이렇게 기하급수적으로 커지면 우리의 눈으로도 한번에 찾을 수 없겠죠.

 

 

순차 탐색의 과정을 살펴보겠습니다.

이렇게, 첫 번째 칸부터 9인지 아닌지 판단하며 나아갑니다.

 

결국 9번째 칸까지 도달하고서야 9라는 숫자를 찾을 수 있겠죠.

 

이를 프로그래밍 언어로 어떻게 구현할 수 있을까요?

 

 

코드)

int SequentialSearch(int* arr, int size, int n) {
  int i;
  for (i = 0; i < size && arr[i] != n; i++) { /*do nothing*/
  };
  if (i == n)
    return -1;
  else
    return i;
}

 

순차 탐색 함수입니다.

배열, 배열의 크기, 찾을 수를 인자로 받아와 찾는 값이 있으면 그 값의 인덱스를 반환하고,

찾는 값이 없는 경우 -1을 반환합니다.

 

코드도 길지 않고 꽤나 쉽게 구현할 수 있습니다.

 

 

 

 

시간 복잡도)

순차 탐색의 시간 복잡도는 어떨까요?

 

1. 최선의 경우

최선의 경우는 찾고자 하는 데이터가 맨 앞에 있는 경우입니다.

이 경우 O(1) 이겠죠.

 

2. 최악의 경우

최악의 경우는 찾고자 하는 데이터가 맨 뒤에 있는 경우입니다.

순차 탐색은 n개의 배열의 맨 앞에서부터 차례대로 탐색을 하기 때문에

이 경우 O(n) 이라고 표현할 수 있습니다.