순차 탐색(Sequential Search)

1. 순차 탐색(Sequential Search) 이란?

• 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

 

연습

- 임의 리스트가 다음과 같이 rand_data_list로 있을 때, 원하는 데이터 위치를 리턴하는 순차탐색 알고리즘 작성

 

def sequential(data, search):
    for index in range(len(data)):
        if data[index] == search:
            return index
    return -1

from random import *

rand_data_list = list()
for num in range(10):
    rand_data_list.append(randint(1, 100))

rand_data_list

출력 : [1, 46, 96, 74, 16, 21, 87, 13, 11, 76]

sequential(rand_data_list, 74)

출력 : 3

 

2. 알고리즘 분석

• 최악의 경우 리스트 길이가 n일 때, n번 비교해야 함 
  • 따라서 시간 복잡도 O(n)