선형 검색, 이진 검색 (단순 검색 알고리즘)

데이터들을 모아둔 곳에서 원하는 값을 가진 원소를 찾아내는 '검색 알고리즘'을 살펴보려고 한다. 먼저 가장 기본적인 접근 방법인 선형 검색, 이진 검색 두 가지를 알아보자.

 

출처 : https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

선형 검색 (linear search)

---

선형 검색 알고리즘은 여러 개의 데이터가 들어있는 리스트에서 찾고자 하는 값이 나올 때까지, 처음부터 하나씩 차례대로 검색하는 알고리즘이다. 말 그대로 100개의 데이터 중 찾으려는 데이터가 100번째에 있다면 100개의 데이터를 다 확인해봐야 찾을 수 있는 것이다. 데이터 개수가 늘어날수록 시간도 당연히 오래걸리게 된다는 단점이 있다.

7개의 데이터 중 선형 검색으로 '4' 찾기

종료 조건

✔️ Success : 검색할 값을 찾은 경우

if (array[index] === 찾는 값)

 

✔️ Fail : 검색할 값을 찾지 못하고 배열의 맨 끝을 지난 경우

if (index === array.length)

 

Javascript로 구현해보기

데이터들이 선형으로 늘어진 배열을 arr, 찾고싶은 값을 key라고 이름을 붙여 매개변수로 지정했다. 배열을 처음부터 쭉 스캔하다가 위에서 언급한 두 가지 종료 조건을 만족하면 그에 따른 결과를 반환하는 식으로 구현했다. 검색할 값을 찾은 경우(성공)에는 해당 인덱스를 최종적으로 반환하고, 검색할 값을 찾지 못한 채 배열의 맨 끝을 지난 경우(실패)에는 false를 반환하도록 했다.

 

function linearSearch(arr, key) {
    for (let i in arr) {
        if (i === arr.length) {
            return false;
        }
        if (arr[i] === key) {
            return i;
        }
    }
}

 

참고

✔️ 최대 검색 횟수 : n회 (=데이터 수) → 끝까지 발견되지 않는 경우

✔️ 평균 검색 횟수 : n / 2회

✔️ 검색량 O(N)

 

 

 

이진 검색 (binary search)

---

이진 검색 알고리즘은 원하는 값을 찾을 때까지 검색할 데이터의 범위를 반씩 줄여가며 찾는 알고리즘이다. 검색 범위를 반으로 나누어 원하는 값이 나올 때까지 계속 검색하는 것이다. 선형 검색과는 다르게 특정 기준에 따라 오름차순 or 내림차순으로 정렬된 리스트를 입력으로 받는다.

 

이진 검색은 정해둔 숫자를 맞추는 게임인 '업다운 게임'을 안다면 바로 이해될 것이다. 업다운 게임 요령(?)으로 숫자 범위의 절반인 숫자를 먼저 외치고, 아니면 그 절반, 또 그 절반...을 외치는 방법이 있다. 예를 들어 1~100이란 범위가 있으면 먼저 50을 기준으로 유추하기 시작 → 더 낮다고 하면 25 → 더 낮다고 하면 13.. 이런 식이다. 이렇게 데이터들 간의 대소관계를 이용하기 때문에, 오름차순이든 내림차순이든 '정렬'이 되어있어야 이 알고리즘으로 검색을 할 수 있다.

 

7개의 데이터 중 이진 검색으로 '4' 찾기

 

종료 조건

✔️ Success : 검색할 값을 찾은 경우

if (array[index] === 찾는 값)

 

✔️ Fail : 검색할 범위가 없는 경우

if (배열처음요소index > 마지막요소index )

 

Javascript로 구현해보기

검색 범위의 맨 앞 요소는 pl, 검색 범위의 맨 마지막 요소는 pr, 그리고 중간지점의 요소는 pc라고 변수명을 지어주었다. 아래 그림처럼 pl, pc, pr은 이전 결과에 의해서 바뀌게 된다. pc는 중간 지점이기 때문에 pl과 pc를 더해 2로 나눈 값을 할당했다. 그리고 인덱스는 정수여야 하기때문에 이 값이 소수로 나올 경우를 고려해 parseInt 메서드를 적용해 주었다.

 

키를 찾은 경우(성공)에는 바로 해당 인덱스(pc)를 반환해주고 반복이 종료된다. 반대로 위의 종료조건에서 말한대로 검색할 범위가 없어지는 경우(실패)에는 false를 반환한다. 여기서 범위가 없어진다는 건 배열의 첫요소 인덱스가 마지막 요소의 인덱스보다 커진다는 말로 바꿔서 이해할 수 있다. 

 

중요한 부분은 배열 첫 요소인 pl, 마지막 요소의 pr이 변하는 부분이다. 그림을 보면 쉽게 이해할 수 있다. 찾고있는 값(key)이 중간값(pc)보다 크다면, 그 다음 반복 때의 범위는 원래의 중간값(pc) 바로 뒤부터 시작된다. pl 이 pc+1로 바뀌는 것이다. 반대로 찾고있는 값(key)이 중간값(pc)보다 작다면, 그 다음 반복 때의 범위는 원래의 중간값(pc) 앞부분이 된다. 즉 마지막 인덱스가 중간값 바로 앞 인덱스가 되는것인데, 코드로 표현하면 pr 이 pc-1로 바뀌는 것이다.

 

function binarySearch(arr, key) {
	let pl = 0;                 // 검색범위 맨 앞 원소 index
	let pr = arr.length - 1;    // 검색범위 맨 뒤 원소 index

    while (true) {
        let pc = parseInt(pl + pr) / 2;    // 중간 원소 index
        if (arr[pc] === key) {
            return pc;                     // 성공!
        } else if (arr[pc] < key) {
            pl = pc + 1;
        } else {
            pr = pc - 1;
        }
        if (pl > pr) {
            return false;
        }
    }
}

 

참고

✔️ 최대 검색 횟수 (log2n)+1 → 선형검색은 n이었는데 훨씬 적어짐

✔️ 평균 log2n

 

요약

---

배운 두 가지 검색 알고리즘을 한 마디로 요약하며 글을 마무리하려고 한다. 코드로 구현하는 과정을 생각해보며 비교해보자!

 

✔️ 선형 검색 (linear search)

: 배열에서 원하는 값을 찾을 때까지 맨앞부터 스캔해 순서대로 검색 (최악의 경우 O(N))

 

✔️ 이진 검색 (binary search)

: 정렬된 배열에서 원하는 값를 찾을 때까지 범위를 반씩 줄여가며 검색 (최악의 경우 (log2n)+1)