검색알고리즘

검색 소개

"ABC"라는 문자열이 있는 데 이 문자열을 포함하는 다른 문자열을 찾고 싶다. 이런 경우 사용되는 알고리즘입니다.

자바스크립트에는 여러가지 내장 함수가 있습니다.
예를들면 indexOf 가있습니다.

• 검색알고리즘이 무엇인지 설명하고
• 배열 선형 검색을 사용해보겠습니다.
• 이진 검색을 알아보고
• 나이브(naive) 문자열 검색과
• KMP 문자열 검색을 알아보겠습니다

선형 검색

배열 안에서 원하는 문자(혹은 숫자)가 있는 지 확인하는 가장 간단한 방법은 무엇일까요. 하나씩 비교하는 방법입니다. [1,4,5,1,2,3] 라는 배열에서 2가 있는 지 찾으려면 1,4,5,1,2,3 순서대로 비교하는 방법이죠.

위의 방법을 선형 검색이라 부릅니다. 그리고 자바스크립트에는 선형검색 기능이 있습니다.

• indexOf
• includes
• find
• findIndex

function linearSearch(arr, val){	// 배열과 찾는 값을 입력 받는다 
    for(var i = 0; i < arr.length; i++){	// 배열 전체를 돌아
        if(arr[i] === val) return i;	// 값과 동일한지 비교하고 찾으면 그 위치를 반환한다. 
    }
    return -1; // 동일한게 없을 경우 -1을 반환한다.
}

linearSearch([34,51,1,2,3,45,56,687], 100)

위의 코드는 선형 검색의 예시 입니다.

선형 검색 빅오는 O(n) 입니다. 배열이 길어질 수록 검색하는데 걸리는 시간도 증가합니다.

이진 검색

• 선형 검색보다 크게 개선된 알고리즘입니다.
• 기본적으로 검색마다 (확인해야할 요소를) 절반씩 제거할 수 있다는 것 입니다.
• 주의해야할 점은 정렬된 배열에서 사용할 수 있는 알고리즘입니다.

대충 감이 오셨겠지만, 정렬된 배열에서 중간의 값과 비교하고 한쪽은 삭제하고 나머지 한쪽에서 / 다시 절반의 위치를 찾아 비교하는 방법을 반복하는 것 입니다. (분할과 정복 개념을 사용합니다)

예시 : [0,1,2,3,4,5,6,7,8,9,10] 중에서 2를 찾자
1. 중간에 arr[5] 와 2를 비교해봅니다 2가 더 작죠? 그럼 arr[6]~arr[10]을 버립니다.
2. 남은 arr[0]~arr[4]까지에서 다시 1번실행합니다

이진 검색 의사코드

1. "정렬된 배열"과 값을 받습니다.
2. 좌측 포인터 (배열 0번)과 우측 포인터 (배열길이-1)를 만들어줍니다.
3. 중간값을 위해 (좌측포인터 + 우측포인터) / 2 를 사용합니다.
4. 찾는 값이 상대적으로 더 크면 좌측 포인터를 당겨오고
5. 찾는 값이 상대적으로 더 작으면 우측 포인터를 당겨오고
   (당겨 온다는 것은 중간 값 위치만큼 당겨오는 걸 말합니다)
6. 만약 같은 값을 찾지 못하면 -1을 반환 한다.

이진 검색 코드 및 빅오

// Original Solution
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]){
            end = middle - 1;
        } else {
            start = middle + 1;
        }
        middle = Math.floor((start + end) / 2);
    }
    if(arr[middle] === elem){
        return middle;
    }
    return -1;
}

// Refactored Version
function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)

이진검색의 빅오는 2가지 케이스로 나뉩니다.
1. O(log n) 평균적 혹은 최악의 상황
2. O(1) 최고의 상황 (바로 중간에 원하는 값이 있을 때)

O(log n)을 살펴보면, 입력 배열이 4개 [0,2,5,7] 일때 최악의 경우(0을 찾아라) 2번만에 찾겠죠. 그리고 입력 배열이 8개 [0,1,2,3,4,5,6,7] 일때 최악의 경우(0을 찾아라) 3번만에 찾을 겁니다.

• N이 4(2^2)일때 2
• N이 8(2^3)일때 3
  이러한 방식으로 늘어납니다. n이 두배가 될 때마다 횟수는 1번 증가합니다.

나이브 문자열 검색

• 긴 문자열에서 특정 문자가 들어갔는지 확인하는 알고리즘
  (wowomgzomg 에서 omg 가 몇번 들어가는지 확인하고 싶어)

의사코드
1. 긴 문자열을 하나씩 반복한다.
2. 짧은 문자열을 반복한다.
3. 일치하는 문자가 없으면 짧은 문자열 반복을 멈춘다.
4. 일치하는 문자가 있으면 짧은 문자열 계속 진행
5. 짧은 문자열 전체가 일치하면 카운트를 1 올려준다
6. 긴 문자열 확인 반복이 끝나면 카운드를 반환한다.

function naiveSearch(long, short){
    var count = 0;
    for(var i = 0; i < long.length; i++){
        for(var j = 0; j < short.length; j++){
           if(short[j] !== long[i+j]) break;
           if(j === short.length - 1) count++;
        }
    }
    return count;
}

naiveSearch("lorie loled", "lol")