[python] 순차탐색 (Sequential Search)

✅ 순차탐색이란

• 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 차례대로 탐색하는 알고리즘

 

✅ 동작 과정

1. 리스트의 맨 앞 데이터와 찾으려는 데이터가 같은 지 탐색
2. 데이터가 같지 않다면 다음 데이터와 찾으려는 데이터가 같은 지 탐색
3. 같은 데이터를 찾기 전까지 2의 과정을 반복

✅ 리스트 내 데이터가 아무리 많더라도 시간만 충분하다면 반드시 원하는 데이터를 찾을 수 있다.

 

✅ 구현

def sq_search(n,target,arr):
    for i in range(n):
        if arr[i]==target:
            return i+1

arr = ['apple','banana','grape','peach','lemon']
n= len(arr)
target = arr[2]

print("{}번째에서 데이터 탐색 종료.".format(sq_search(n,target,arr)))

 

✅ 코드 결과

 

✅ 시간 복잡도 (Big-O)

• 데이터의 정렬 여부와 상관없이 맨 앞에 있는 데이터부터 하나씩 차례대로 탐색함
• 따라서 리스트 내 데이터가 N개 있다면 비교 연산을 최대 N번 수행해야함
• 최악의 경우 순차 탐색의 시간 복잡도는 O(N)이다.