[Algorithms] Sequential Search | 순차 탐색

Sequential Search

 

순차 탐색

 

- 리스트의 처음 혹은 끝 부분부터 반대편까지 순차적으로 원소를 검색해나간다.
- 정렬되지 않은 리스트를 검색할 때 주로 사용되는 방법이다.
- 정렬된 리스트의 경우, Binary Search 알고리즘(\(\Theta(\log n)\))을 사용하는 것이 실행 시간 측면에서 더 효율적이다.

* Time complexity of Sequential Search: \(\Theta(n)\)

---

Implementation (구현)

 

C++

template <typename T>
void SequentialSearch(const T list[], const int size, T key, int& location) {
	location = 0;
	while (location < size && list[location] != key)
		location++;
	if (location >= size) {
		location = -1;
		// 예외처리로 구현하기
}


template <typename T>
void SequentialSearch_backward(const T list[], const int size, T key, int& location) {
	location = size - 1;
	while (location > -1 && list[location] != key)
		location--;
	if (location < 0)
		location = -1;
	// 예외처리로 구현하기
}