순차 탐색(Sequential Search)

🌟 다양한 탐색 방법

리스트 형태 👉 순차 탐색, 이진 탐색

트리 형태 👉 이진 탐색 트리, 2-3-4 트리, 레드-블랙 트리, B-트리

해시 테이블 👉 해시 함수, 충돌 해결 방법

 

🟩 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로("순차") 비교하면서 원하는 값을 갖는 원소를 찾는 방법

// A[] : 입력배열
// n : 입력 크기 (탐색할 데이터의 갯수)
// x : 탐색 키

SequentialSearch(A[ ], n, x){
	i = 0;
    while (i < n && A[i] != x)
		i = i + 1;
	return (i);
}

// x가 배열 내에 존재하면 인덱스, 아니면 n을 반환

 

 

🌟 삽입 및 삭제

 

🟩 시간 복잡도

탐색, 삭제 : O(n)

삽입 : O(1)

 

🟩 정렬되지 않고 크기가 작은 데이터에 적합

모든 리스트 형태의 입력에 적용 가능 👉 비정렬 데이터 탐색에 적합

탐색과 삭제에 O(n)의 시간 필요 👉 데이터가 큰 경우에는 부적합