[검색 알고리즘] 선형 검색

선형 검색(Linear Search)

배열에서 검색하는 방법 중 가장 기본적인 알고리즘입니다.

 

직선(선형)으로 늘어진 배열에서 검색하는 경우 원하는 원소를 찾을 때까지 맨 앞에서부터 순서대로 검색하는 알고리즘입니다.

---

2

4

1

6

7

3

5

가령 위와 같은 배열이 있다고 가정해봅시다. 우리는 원소 3을 찾고 싶습니다.

그렇다면 맨 앞 배열의 0번자리부터 스캔을 시작하고, 6번째 스캔에서 3을 찾아내게 됩니다.

원하는 3을 찾았으니 검색은 성공하고 알고리즘은 종료되겠죠.

 

그러나 8을 찾는다고 가정해보겠습니다.

앞에서부터 스캔을 하다가 6번자리까지 지나도 보이지 않으니 배열의 맨 끝 원소를 지나가게 되고, 알고리즘은 검색이 실패한 채 종료됩니다.

 

위의 설명과 같이 선형 검색이 종료되는 조건은 2가지가 있습니다.

1. 검색에 실패하거나(검색할 값을 찾지 못한 채 배열의 끝까지 검색한 경우)

2. 검색에 성공하거나(검색할 값과 같은 원소를 찾은 경우)

---

이처럼 선형 검색은 원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법입니다.

 

그러나 선형 검색은 검색을 반복할 때마다 종료 조건 2가지를 판단하게 됩니다. 이는 배열이 커지면 커질수록 비효율적으로 변하게 되죠.

그런데 위 종료되는 조건 판단 횟수를 절반으로 줄일 수 있는 방법이 있습니다.

 

바로 보초법입니다. 선형검색에 기능을 업데이트 했다고 생각하시면 됩니다.

배열의 맨 끝에 찾고자 하는 원소 값을 추가하면 됩니다. 이를 보초라고 합니다.

2

4

1

6

7

3

5

8

기존의 배열의 맨 끝에 8을 추가했습니다. 이렇게 되면 조건 1번은 만족하지 않으니 어떻게든 2번만 만족하면 되겠죠.