[ALGORITHM] 21. 선형 탐색

선형 탐색(Linear Search)은 배열이나 리스트와 같은 자료 구조에서 특정 원소를 찾기 위해 처음부터 끝까지

순차적으로 탐색하는 알고리즘을 말하며, 검색할 요소들이 정렬되어 있지 않은 경우에도 적용할 수 있다.

 

template<typename T>
bool linear_search(const std::vector<T>& data, T target) {

	for (const T& element : data) {

		if (element == target) {

			return true;
		}
	}

	return false;
}

 

 

특징

 

1. 순차적 탐색 : 시작부터 끝까지 각 원소를 비교하면서 찾고자 하는 값을 찾을 때까지 진행한다.

2. 시간 복잡도 : 최악의 경우, 탐색하려는 원소가 배열의 맨 끝에 있거나 원소가 존재하지 않는 경우

전체 배열을 끝까지 탐색해야 하므로 시간 복잡도는 O(n)이다.

3. 간단하고 직관적 : 간단하게 구현할 수 있으며 추가 메모리가 필요하지 않다.

 

 

장점

 

1. 정렬되지 않은 데이터에 적합 : 다른 정렬 알고리즘처럼 특정 조건 없이 데이터가 정렬되지 않았을 때도 사용할 수 있다.

2. 추가 메모리 사용 없음 : 배열이나 리스트의 각 원소를 하나씩 비교하면서 탐색하기 때문에 공간 복잡도가 낮다.

 

 

단점

 

1. 시간 복잡도가 높음 : 최악의 경우 배열이나 리스트의 모든 원소를 확인해야 하므로 시간 복잡도가 O(n)이다.

이는 큰 데이터를 다룰 때 효율적이지 않을 수 있다.

2. 정렬된 데이터에 적합하지 않음 : 데이터를 정렬하지 않고 탐색하는 데에는 유용하지만,

데이터가 이미 정렬된 경우에는 이진 탐색과 같은 다른 알고리즘이 더 효율적이다.