[Python] 순차 탐색(Sequential Search)

순차 탐색(Sequential Search)

순차 탐색

• 어떤 데이터는 정렬되지 않은 상태로 존재하고, 어떤 데이터는 정렬된 상태로 존재한다.
• 이 두 경우에 데이터를 찾는 방법은 조금 다르다.

 

① 정렬되지 않은 집합에서의 순차 탐색

검색 성공

• 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다.

 

검색 실패

• 첫 번째 데이터부터 차례로 비교해서 찾지 못할 경우, -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다.

 

def seqSearch(ary, fData) :
    pos = -1
    size = len(ary)
    print('## 비교한 데이터 ==> ', end = '')
    for i in range(size) :
        print(ary[i], end = ' ')
        if ary[i] == fData :
            pos = i
            break
    print()
    return pos

dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

findData = int(input('* 찾을 값을 입력하세요. --> '))
print('배열 -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
    print(findData, '(이)가 없네요.')
else :
    print(findData,'(은)는 ', position, '위치에 있음')

 

* 찾을 값을 입력하세요. --> 105
배열 --> [188, 150, 168, 162, 105, 120, 177, 50]
## 비교한 데이터 ==> 188 150 168 162 105 
105 (은)는  4 위치에 있음

* 찾을 값을 입력하세요. --> 100
배열 --> [188, 150, 168, 162, 105, 120, 177, 50]
## 비교한 데이터 ==> 188 150 168 162 105 120 177 50
100 (이)가 없네요.

 

② 정렬된 집합에서의 순차 탐색

검색 성공

• 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다.

 

검색 실패

• 첫 번째 데이터부터 차례로 비교해서 찾을 데이터보다 큰 데이터를 만나도 못 찾으면 이후는 검색할 필요 없이 검색에 실패한 것이다. 이때는  -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다.

 

def seqSearch(ary, fData) :
    pos = -1
    size = len(ary)
    print('## 비교한 데이터 ==> ', end = '')
    for i in range(size) :
        print(ary[i], end = ' ')
        if ary[i] == fData :
            pos = i
            break
        elif ary[i] > fData :
            break
    print()
    return pos

dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

dataAry.sort()
findData = int(input('* 찾을 값을 입력하세요. --> '))
print('배열 -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
    print(findData, '(이)가 없네요.')
else :
    print(findData, '(은)는 ', position, '위치에 있음')

 

* 찾을 값을 입력하세요. --> 150
배열 --> [50, 105, 120, 150, 162, 168, 177, 188]
## 비교한 데이터 ==> 50 105 120 150
150 (은)는  3 위치에 있음

* 찾을 값을 입력하세요. --> 70
배열 --> [50, 105, 120, 150, 162, 168, 177, 188]
## 비교한 데이터 ==> 50 105
70 (이)가 없네요.

 

순차 탐색의 시간 복잡도

정렬되지 않은 집합

• 정렬되지 않은 집합의 순차 탐색은 찾는 데이터가 앞쪽에 배치되어 있는 운이 좋은 경우에는 몇 번의 비교만으로 검색을 완료할 수 있다.
• 하지만, 가장 뒤쪽에 배치되거나 아예 없는 데이터를 모든 데이터와 비교해야 한다.
• 데이터 개수가 `n`개라면 시간 복잡도는 `O(n)`으로 표현된다.

 

정렬된 집합

• 정렬된 집합의 순차 탐색 역시 운이 좋게 찾을 데이터가 앞쪽이라면 몇 번의 비교만으로 완료할 수 있다.
• 검색할 데이터가 없는 경우에도 데이터의 크기가 작다면 앞쪽만 검색한 후 검색 실패를 효율적으로 확인할 수 있다.
• 하지만, 최악의 경우에는 맨 마지막까지 검색할 수 있으므로 시간 복잡도는 `O(n)`으로 표현해야 한다.