[탐색과 정렬] 순차 탐색

탐색
여러 개의 자료 중에서 원하는 것을 찾아내는 것

정렬
주어진 자료를 순서에 맞춰 나열하는 것

 

순차 탐색

sequential search

리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색한다.

선형 탐색(linear search)이라고도 부른다.

 

코드

def sequential(num, list):
    for i in range(0, len(list)):
        if num == list[i]:
            return i
    return -1

계산 복잡도는 최악의 경우 O(n)이다.

자료를 일일이 비교하지 않고 좀 더 효율적으로 탐색을 하기 위해서는 자료를 정렬할 필요성이 있다.

 

 

참고 문서

https://thebook.io/006935/part03/ch07/