[알고리즘][C++] 선형검색 (Linear Search)

개요

선형검색(Linear Search) 알고리즘은 배열을 처음부터 끝까지 읽어보고 찾고자 하는 키 값을 찾는 간단한 알고리즘이다.

---

코드

void Linear_Search(int arr[], int size, int key){
	int find = 0;
	for(int i=0;i<size;i++){
		if(arr[i] == key) find = 1;
	}
	if(find == 1) cout << "찾았습니다!";
	else cout << "배열에 키 값이 없습니다.";
}

 

함수의 매개변수로는 배열과 배열의 크기, 찾고자 하는 키 값을 전달받는다.

배열에 키 값이 있으면 find 값을 1로 바뀌게 설정해놓았다

---

실행 결과

main 함수에 이것저것 추가해 주고 코드를 돌려보면 다음과 같이 잘 작동하는 것을 볼 수 있다.

 

 

---

분석

• 평균적인 경우의 수행시간: $ \frac {n}{2} $ 회
• 최악의 경우 수행시간: $ \Theta (n) $