탐색알고리즘(1) Sequential Search (순차 탐색)

정렬 알고리즘 5개를 마치고, 이번 포스팅은 탐색 알고리즘의 시작으로 순차 탐색에 대한 포스팅이다. 탐색 알고리즘은 말그대로 여러 데이터 중에서 내가 원하는 데이터를 찾아내는 알고리즘이다. 이 중 순차탐색은 알고리즘/자료구조 강의 전체를 통틀어서 가장 쉬웠던 부분이다. 그냥 python 기본 문법 공부하는 정도의 난이도랄까..?ㅎㅎㅋ 간단히 포스팅해보도록 하겠다-!

Sequential Search 순차 탐색

순차탐색은 원하는 데이터를 찾고자할 때, 데이터가 담겨있는 리스트에의 맨 처음부터 하나하나 순서대로 비교해가며 탐색하는 알고리즘이다. sequential search 또는 linear search 알고리즘이라고도 불린다.

(뭔가 더 설명을 쓰고 싶지만 진짜 이게 끝이다. ,,,ㅎㅋㅋ)

알고리즘 구현

def sequencial(data_list, search_data):
    for index in range(len(data_list)):
        if data_list[index] == search_data:
            return index
    return -1

#test code
from random import *
rand_data_list = ()
for num in range(10):
    rand_data_list.append(randint(1, 100))

sequencial(rand_data_list, 4)

리스트의 0번 index부터 하나하나 내가 찾고자하는 값과 비교해가며 일치하면 그 index번호를 return하고, 끝까지 다 돌아도 찾는 데이터가 없다면 -1을 return한다.

시간복잡도

최악의 경우, list의 길이가 $n$일 때 최대 $n$번까지 비교해야하므로, 시간복잡도는 빅오표기법으로 표기하면 $O(n)$이라고 할 수 있다.