[JAVA] 배열의 선형검색, 보초법

선형 검색(linear search) 이란 요소가 직선 모양으로 늘어선 배열에서 원하는 키 값을 요소를 만날 때까지

맨 앞부터 순서대로 요소를 검색하는 알고리즘 입니다.

---

배열 검색의 종료 조건

다음과 같은 배열이 있습니다.

 

조건 1 : 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우

조건 2 : 검색할 값과 같은 요소를 발견한 경우

숫자 7을 찾는 방법입니다.

구현해보기

위의 코드를 보면 검색성공과 실패의 두가지 종료조건을 만족하여 코드를 구현하였습니다.

 

보초법

선형검색은 위의 종료조건 두가지를 모두 판단해야 합니다.

'티끌 모아 태산' 이라는 말이 있듯이 두가지의 종료 조건을 검사하는 비용은 결코 무시할 수 없습니다.
보초법은 이 비용을 반(50%)로 줄이는 방법입니다.

검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장합니다.

이때 저장하는 값을 보초라고 합니다.

이렇게 하면 원하는 키값을 찾지 못했을 때를 판단하는 종료 조건이 없어도 됩니다.

 

위의 배열을 사용하여 예제를 살펴 보겠습니다.

위의 코드에서 search메소드는 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우가 보초값으로 인하여 존재하지 않습니다.

따라서 반복 종료에 대한 판단 횟수는 실제로 절반으로 줄어듭니다.

while문에 의한 반복이 완료되면 찾은 인덱스의 값이 보초인지 원래 데이터인지 판단해야합니다.

삼항연산자를 사용하여 반환시켜 줍니다.

---

이상으로 선형 검색에 대하여 알아보았습니다.