선형 검색

이번에 소개할 알고리즘은 검색입니다. 주어진 컬렉션 내부를 정렬하는 것 만큼 유용하고 많이 쓰이는게 컬렉션 내부에서 요소를 찾아내는 것 입니다.

---

1. 검색 알고리즘

검색 알고리즘은 컬렉션에서 원하는 요소를 찾아내는 알고리즘입니다. 검색은 보통 조건을 n개 주고 그 조건에 해당하는 요소를 반환하게됩니다. 그 조건에 부합하는 요소를 키(key)라고 하며, 키와 일치하는 값이 컬렉션 내부에 있으면 검색이 성공한 것이고, 일치하는 값이 없다면 검색에 실패했다고 볼 수 있습니다.

 

 

2. 선형 검색

선형 검색은 가장 기본적이고 간단한 알고리즘입니다. 심지어는 프로그래밍 입문해서 지금까지도 숨쉬듯이 사용했을 수도 있습니다. 다만 이름 선형 검색이라는 것은 이번에 처음 알게된 사실일 수도 있습니다.

선형 검색은 요소가 직선 형태로 이루어진 컬렉션에서 키와 일치하는 요소를 찾을 때 까지 맨 처음부터 순서대로 검색하는 방식입니다. 선형 검색은 순차 검색이라고 부르기도 합니다.

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("검색 실패");
}

import {linearSearch} from './study-code/search/linear-search.js';

const arr = [32, 44, 5, 4, 7, 13, 17, 30, 25, 51];

linearSearch(arr, 30);

검색에 성공한 모습입니다.

위 코드를 보면 종료 조건이 2가지가 있습니다.

조건 1. 배열에서 키와 일치하는 요소값을 찾은 경우
조건 2. 배열을 끝까지 다돌았는데 일치하는 요소값이 없는 경우

 

배열의 끝까지 가는 경우 조건 2까지 일일히 검사해야합니다. 이게 언뜻 봐서는 별거 아닌 조건 판정같지만, 이런 조건들이 쌓이고 쌓여 큰 프로그램을 이룰 때 이 판정이 갖는 비용은 무시할 수 없는 크기입니다.

 

 

 

3. 보초법

위에서 본 조건이 두개 있는 경우를 해결하기 위해 등장한 방법이 보초법(Sentinel Method)입니다. 이 방식은 다음 조건 1만을 이용합니다.

조건 1. 배열에서 키와 일치하는 요소값을 찾은 경우

 

보초법의 원리는 1) 검색하고자 하는 배열의 맨 끝에 인덱스를 하나 추가하고 그 요소로 키 값을 저장합니다. 이 저장한 값을 보초(Sentinel)라고 합니다. 2) 이렇게 하면 원래 배열에 키와 일치하는 요소가 없더라도 마지막 인덱스에서 찾을 수 있게 됩니다. 3) 마지막 인덱스에서 찾았을 경우 검색 실패함으로 판정 합니다. 이렇게 하면 조건 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) ? '보초법: 검색 실패' : '보초법: 검색 성공');
}

import {linearSearch} from './study-code/search/linear-search.js';
import {sentinelMethodLinearSearch} from './study-code/search/sentinel-method-linear-search.js';

const arr = [32, 44, 5, 4, 7, 13, 17, 30, 25, 51];

linearSearch(arr, 30);
sentinelMethodLinearSearch(arr, 10, 6);

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/search/linear-search.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록

https://github.com/Bam-j/algorithm-study/blob/main/study-code/search/sentinel-method-linear-search.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록