Linear Search (선형검색)

선형검색이란?

• 선형(직선) 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 처음(맨 앞)부터 순서대로 검색하는 알고리즘

예제

다음과 같은 배열 주어졌을 때, 배열 내의 원소 중에서 7을 찾아라
[1,2,3,4,5,6,7,8,9,10]

 

 

위의 예제에서 선형 검색의 종료 조건은 다음과 같다.

검색할 값과 같은 요소를 발견한 경우 (검색 성공)
검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (검색 실패)

이 경우, 종료를 위한 판단 조건은 2개이다.

---

이때 종료를 위한 판단 조건을 줄일 수 있는 방법이 보초법이다.

검색할 키 가밧을 배열의 맨끝에 추가한다. 이 값을 보초(sentinel)라고 한다.

이 경우, 선형 검색의 종료는 무조건 검색할 값의 같은 요소를 발견함으로 1개만 존재한다.

검색할 값과 같은 요소를 발견한 경우 (검색 성공)
단, 검색 실패를 판단하는 기준은 반복문의 회수와 주어진 배열의 길이를 비교하여 판단한다.

 

 

시간복잡도

• O(N)
• 최악의 경우 모든 원소를 다 탐색해야한다.