[자료구조] 탐색 (search)

탐색이란?

자료구조에서 탐색이란 여러 개의 데이터 중 원하는 데이터를 찾는 작업을 말합니다.

탐색은 크게 두 가지로 나눌 수 있습니다.

• 정렬되지 않은 상태에서 탐색
• 정렬된 상태에서 탐색

 

이번 포스팅에서는 정렬되지 않은 상태에서의 탐색을 살펴보겠습니다.

 

순차 탐색

정렬되지 않은 상태에서 탐색을 하려면 어떻게 해야 할까요? 리스트의 첫 번째 요소부터 하나씩 순차적으로 요소를 방문해서 비교를 하면 됩니다.

int seq_search(int key, int low, int high) {
	for(int i = low; i <= high; i++) {
		if(list[i] == key) {
			return i;
		}
	}
	return -1;
}

 

순차 탐색의 시간복잡도

순차 탐색의 시간복잡도는 데이터의 개수가 $n$개 있다고 가정하면 $O(n)$이 소요됩니다.