순차검색(Sequential Search), 선형검색 알고리즘(linear search algorithm)

• 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것
• 시간복잡도 O(n)

구현코드

def sequential_search(s, key):
    i = 0
    while i < len(s):
        if s[i] == key:
            return i
        i += 1
    return -1


def sequential_search2(s, key):
	for idx, val in enumerate(s):
		if val == key:
			return idx
	return -1

순차탐색 vs 이진탐색

• 시간복잡도를 비교하면 순차탐색 O(n), 이진탐색(O(log n)으로 이진 탐색이 훨씬 빠르다.
• 단, 이진탐색은 데이터가 정렬되어 있어야 한다는 전제 조건이 있다.
• 일반적인 정렬 알고리즘은 O(n log n)의 시간 복잡도를 가지기에 이진탐색이 반드시 좋다고 할 수 없다.
• 따라서 상황에 맞는 알고리즘을 선택하는 것이 중요하다.

reference

• 위키백과
• 순차 탐색 알고리즘(Linear Search)