검색 알고리즘
검색 알고리즘은 컬렉션에서 원하는 요소를 찾아내는 알고리즘입니다. 검색은 보통 조건을 n개 주고 그 조건에 해당하는 요소를 반환하게됩니다. 그 조건에 부합하는 요소를 키(key)라고 하며, 키와 일치하는 값이 컬렉션 내부에 있으면 검색이 성공한 것이고, 일치하는 값이 없다면 검색에 실패했다고 볼 수 있습니다.
선형 검색
선형 검색은 가장 기본적이고 간단한 알고리즘입니다. 심지어는 프로그래밍 입문해서 지금까지도 숨쉬듯이 사용했을 수도 있습니다. 다만 그 방식이 선형 검색이라는 이름을 가졌다는 것은 이번에 처음 알게된 사실일 수도 있습니다.
선형 검색은 요소가 직선 형태로 이루어진 컬렉션에서 키와 일치하는 요소를 찾을 때 까지 맨 처음부터 순서대로 검색하는 방식입니다. 선형 검색은 순차 검색이라고 부르기도 합니다.
선형 검색 구현
export const linearSearch = (arr, key) => {
//주어진 배열을 처음부터 끝까지 순회
for (let i = 0; i < arr.length; i++) {
//키값과 일치하는 요소가 있으면 검색 성공(조건1)
if(key === arr[i]) {
console.log("검색 성공");
return 0;
}
}
//순회를 다돌아도 일치하는 값이 없으면 검색 실패(조건2)
console.log("검색 실패");
}위 코드를 보면 종료 조건이 2가지가 있습니다.
- 조건 1: 배열에서 키와 일치하는 요소값을 찾은 경우
- 조건 2: 배열을 끝까지 다돌았는데 일치하는 요소값이 없는 경우
배열의 끝까지 가는 경우, 조건 2까지 일일히 검사해야합니다. 이게 언뜻 봐서는 별거 아닌 조건 판정같지만, 이런 조건들이 쌓이고 쌓여 큰 프로그램을 이룰 때 이 판정이 갖는 비용은 무시할 수 없는 크기입니다.
보초법
위에서 본 조건이 두개 있는 경우를 해결하기 위해 등장한 방법이 보초법(Sentinel Method)입니다. 이 방식은 다음 조건 1만을 이용합니다.
- 조건 1: 배열에서 키와 일치하는 요소값을 찾은 경우
보초법의 원리는 다음과 같습니다.
- 검색하고자 하는 배열의 맨 끝에 인덱스를 하나 추가하고 그 요소로 키 값을 저장합니다. 이 저장한 값을 보초(Sentinel)라고 합니다.
- 보초를 넣으면 원래 배열에 키와 일치하는 요소가 없더라도 마지막 인덱스에서 찾을 수 있게 됩니다.
- 마지막 인덱스에서 찾았을 경우 검색 실패함으로 판정 합니다. 이렇게 하면 조건 2없이도 조건 1만 가지고 선형 검색을 할 수 있는 것 입니다.
//인자로 검색 대상 배열, 배열의 보초를 넣은 인덱스, 찾을 키 이용
export const sentinelMethodLinearSearch = (arr, sentinel, key) => {
let i = 0;
//배열의 마지막 인덱스에 키 값 추가
arr[sentinel] = key;
while (true) {
if(key === arr[i]) {
break;
}
i++;
}
//만약 인덱스 i가 보초가 저장된 인덱스와 같다면 검색 실패
console.log((i === sentinel) ? '보초법: 검색 실패' : '보초법: 검색 성공');
}