자료의 탐색 - 순차 탐색(Sequential search)

순차탐색(Sequential search)

데이터의 첫 부분(선두)부터 순서대로 탐색키와 데이터를 비교하여 원하는 데이터를 찾는 방법.

 

ex) 책에서 원하는 자료를 찾고자 할 때 처음부터 차례대로 한 장씩 열어 보고 원하는 자료를 찾는 방법이다.

첫 번째 장의 자료가 찾고자 하는 자료인지를 보고 만일 찾는 자료가 아니라면 두 번째 장의 자료를 열어 보고 찾는 자료가 아니라면 다시 다음 장을 살펴보는 방법이다.
책 속의 자료들의 배치에 대한 아무런 정보 없이 원하는 자료를 찾는 극히 단순하며 정확한 방법이다.

→ 즉, 자료를 처음부터 마지막까지 순서대로 탐색하는 가장 간단하고 이해하기 쉬운 직접적인 탐색 방법이다.

순차탐색(Sequential search) 탐색방법

 ① 자료의 집합에서 첫 번째 원소부터 시작하여 키 값과 일치하는지 비교한다.

 ② 찾는 키 값이 일치하는 원소를 찾으면, 그 원소가 몇 번째 원소인지를 반환한다.

 ③ 찾는 키 값이 일치하지 않으면, 위 과정을 반복한다.

 ④ 만일 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이라고 판단한다.

순차탐색(Sequential search) 의사코드

int sequential_search2(int key, int low, int high) {    int i;      list [high + 1] = key //키 값을 찾으면 종료      for(i = low; list [i] ! = key; i++);      if(i == (high + 1)) return – 1; //탐색 실패      else return i; //탐색 성공 }

순차탐색(Sequential search) 예제

문제: 10장으로 구성된 묶음 책으로 각 장에 수가 다음과 같이 임의로 배치되어 있다고 가정한다.

1)찾고자 하는 수가 78일 경우

2)찾고자 하는 수가 3인 경우

순차탐색(Sequential search) 비교횟수, 특징

비교횟수
   -최선의 경우 ⇒ 1
   -최대 비교 횟수 ⇒ n
   -탐색의 평균 비교 횟수 ⇒ n+1 / 2
   -시간복잡도 ⇒ O(n)

특징

   -자료가 정렬되어 있지 않아도 된다.

   -적은 자료에서 검색할 때 효율적이다.

   -검색 알고리즘이 간단하나 속도가 느리다.