[알고리즘] 선형 탐색 (Linear Search)

선형 탐색은 매우 간단한 알고리즘이다.

다른 개념을 공부할 때 자주나와서 먼저 공부하려고 한다.

 

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

선형 탐색(Liner Search)은 배열에서 데이터를 찾는 알고리즘이다. 이진 탐색과 달리 데이터가 순서 없이 뒤죽박죽 나열된 경우에도 적용할 수 있다.  찾는 방식은 단순히 배열 앞쪽부터 순서대로 데이터를 조사한다.

 

선형 탐색

1부터 9까지 정수가 랜덤으로 배열에 담겨 있다고 가정해 보자

 

선형 탐색

그 중 숫자 6을 찾아 보겠다.

 

선형 탐색

단순하다. 배열의 가장 먼저인 왼쪽 부터 차례대로 6이 맞는지 확인하면 된다.

첫 숫자는 2임으로 넘어간다.

 

선형 탐색

다음 숫자는 7이다. 6이 아님으로 넘어간다.

 

선형 탐색

다음은 5 마찬가지로 넘어간다.

 

선형 탐색

이런식으로 6이 나올때 까지 쭉 진행하면 된다. 6과 일치하는 데이터를 찾으면 탐색을 종료한다.

 

여기까지가 선형 탐색이다. 매우 간단한 알고리즘이다.

---

⏱️ 시간복잡도

선형 탐색은 데이터의 처음부터 순서대로 비교를 반복한다. 따라서 데이터가 많고 찾는 데이터가 끝에 있거나 없는 경우에는 비교 횟수가 많아져서 시간이 오래걸린다.

 

데이터 수가 n이라면 계산 시간은 O(n)이다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠