순차 탐색(Sequential Search) 이론과 파이썬 구현

순차 탐색(Sequential Search)

 

순차 탐색(Sequential Search)은 탐색 방법에서 가장 간단하고 직접적인 탐색 알고리즘입니다.

 

순차 탐색은 리스트의 요소를 처음부터 마지막까지 하나씩 검사해서 원하는 값을 찾는 방법입니다.

 

원하는 값은 key로 주어지고 탐색의 범위는 low와 high로 주어집니다.

 

탐색에 성공하면 원하는 값의 인덱스를 반환하고 그렇지 않으면 -1을 반환합니다.

 

순차 탐색은 선형 탐색(linear search)이라고도 합니다.

 

a=[1, 3, 5, 7, 2, 4, 6]

def Sequential_Search(key, low, high):

    for i in range(low, high+1):
        if a[i] == key:
            return i

    return -1

# 출력>>6
print(Sequential_Search(6, 0, 6))

# 출력>>-1
print(Sequential_Search(10, 0, 6))

# 출력>>0
print(Sequential_Search(1, 0, 3))

# 출력>>-1
print(Sequential_Search(2, 0, 3))

함수 Sequential Search이 순차 탐색 알고리즘입니다.

 

Sequential_Search(6, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key 6의 인덱스를 찾습니다.

Sequential_Search(10, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key 10의 인덱스를 찾습니다.

Sequential_Search(1, 0, 3)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 3까지에서 key 1의 인덱스를 찾습니다.

print(Sequential_Search(2, 0, 3)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 3까지에서 key 2의 인덱스를 찾습니다.

 

a=[1, 3, 5, 7, 2, 4, 6]

def Sequential_Search(key):
    for i in range(len(a)):
        if a[i] == key:
            return i

    return -1

# 출력>>6
print(Sequential_Search(6))

# 출력>>-1
print(Sequential_Search(10))

 

탐색의 범위를 low와 high로 설정하지 않고 리스트 전체에서 key를 찾는 순차 탐색 알고리즘입니다.

 

가장 많이 사용하는 순차 탐색 알고리즘 코드입니다.

 

정렬된 리스트와 정렬되어 있지 않은 리스트에 모두 사용 가능합니다.

 

순차 탐색은 탐색에 성공하면 평균 (n+1)/2번 비교하고 탐색에 실패하면 n번 비교합니다.

 

순차 탐색 알고리즘의 시간 복잡도는 O(n)입니다.

 

---

만약 리스트가 정렬되어 있다면 위의 코드는 오랜 시간이 걸려서 비효율적인 방법입니다.

 

그래서 정렬되어 있는 리스트에서는 좀 더 간단하게 순차 탐색을 할 수 있습니다.

 

정렬된 리스트는 순차 탐색을 실행하는 도중 key 값보다 큰 항목을 만나면 그 뒤의 항목들은 모두 key 값이 아니라는 점을 기억해야 합니다.

 

a=[1, 3, 5, 7, 9, 11, 13]

def Sequential_Search(key):
    for i in range(len(a)):
        if a[i] > key:
            return -1
        
        if a[i] == key:
            return i

    return -1
# 출력>>2
print(Sequential_Search(5))

# 출력>>-1
print(Sequential_Search(10))

# 출력>>-1
print(Sequential_Search(17))

리스트에 key 값이 존재하거나 key 값이 리스트의 맨 마지막 요소보다 큰 경우 위의 순차 탐색과 같습니다.

 

하지만 해당 항목이 리스트에 존재하지 않고 리스트의 맨 마지막 요소보다 작아서 비교 횟수가 반이 됩니다.

 

그러나 시간 복잡도는 O(n)으로 동일합니다.