순차 검색

순차 검색

• 일렬로 되어 있는 자료를 순서대로 검색하는 방법

  • 가장 간단하고 직관적인 검색 방법
  • 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함
  • 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격하게 증가하여 비효율적임

• 검색 과정

  • 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 찾는다.
  • 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.
  • 자료구조의 마지막에 이를 때까지 검색대상을 찾지 못하면 검색을 종료한다.

• 찾고자 하는 원소의 순서에 따라 비교회수가 결정됨

  • 첫번째 원소를 찾을때는 1번 비교, 두번째 원소를 찾을때는 2번 비교
  • 정렬되지 않은 자료에서의 순차 검색의 평균 비교 회수
    • (1/n)*(1+...+n) = (n+1)/2\

• 시간 복잡도 : O(n)

• 정렬되어 있는 경우

  • 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교회수가 반으로 줄어든다.
  • 시간복잡도 : O(n)

def sequentialSearch(lst,n,key):
    i = 0
    while i <n and a[i] !=key :
        i += 1 
    if i<n : 
        return i
   	else :
        return -1 

def sequentialSearch2(lst,n,key) :
    i = 0
    while i<n and a[i]<key :
        i +=1 
    if i<n and a[i] == key:
        return i
   	else :
        return -1