선형 검색 (Linear Search)

선형 검색이란, 분류되지 않은 데이터 목록에서 사용하기에 좋은 검색 방법으로 JS에서는 indexOf,includes,find,findIndex등의 메소드가 선형 검색의 기능을 수행한다. 이 선형 검색은 데이터가 모인 집합의 처음부터 끝까지 하나씩 순서대로 비교해서 원하는 값을 찾아내는 알고리즘이다.

선형 검색의 Big-O

선형 검색은 첫 부분에서 시작해서 끝부분으로 이동하면서 한 번에 하나의 항목을 확인하게 되는데 그렇기 때문에 5개의 요소가 있든, 100만개의 요소가 있든 하나씩 비교하기 때문에 요소의 크기에 비례하게 된다. 우리가 찾는 값이 첫 비교에 바로 나타난다면 O(1)로 최고의 시간 복잡도가 나오겠지만 이런 경우는 드물다. 보통은 요소에 비례하기 때문에 O(n)의 시간 복잡도를 가진다.

선형 검색이 종료되는 조건

• 찾아야 하는 값을 찾지 못하고 배열의 끝을 지나간 경우
• 찾아야 하는 값과 같은 요소를 발견한 경우

이진 검색 (Binary Search)

정렬된 데이터 목록에서 원하는 값을 찾고 싶을 때 사용하기에 좋은 검색 방법이다. 선형은 순서대로 하나씩 비교하면서 값을 찾아갔다면, 이진 검색은 찾고자 하는 값이 있으면 배열에서 중간 값을 찾고 그 중간 값과 비교해서 중간 값보다 찾고자 하는 값이 작으면 오른쪽의 절반을 날리고, 반으로 작아진 배열에서 또 다시 중간 값을 찾아 그 중간 값과 찾고자 하는 값을 다시 비교해서 처음과 같이 필요없는 항목들을 날리며 값을 찾을 때까지 반복하게 된다. 그렇기 때문에
선형 검색보다 더 빠르게 작업을 완료할 수 있다. 하지만 분류된 데이터(오름차순, 내림차순)에서만 사용이 가능하다.

구현 방법

이진 검색의 기본적인 개념은 '분할 정복(dividing and conquering)이다. 그래서 배열을 두 부분으로 나눈다. 그 다음에는 보통 중간에 있는 중간점을 선택하고 찾는 값이 중간점을 기준으로 좌측 절반과 우측 절반 중 어느 쪽에 있는지 확인한다.

function binarySearch(arr,elem) {
    let start = 0;
    let end = arr.length-1;
    let 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;
}

이진 검색 Big-O

이진 검색도 마찬가지로 내가 찾고자 하는 값이 제일 처음으로 선택한 항목일 경우에는 O(1)의 시간 복잡도를 갖는다. 하지만 이는 매우 드물기 때문에 보통의 경우는 O(log n)의 시간 복잡도를 갖는다. 왜냐, 이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되기 때문에 검색에 필요한 비교 횟수의 평균 값은 log n이 된다.
만약 16크기의 배열이 있어 log2의 16은 뭐가 될까? '4'가 된다. 2의 네제곱이 16이기 때문에 그럼 16의 두배인 32는? '5'가 된다. 따라서 n의 크기를 두배로 불릴 때마다 그냥 한 단계가 더 추가되는 것이다. Big-O차트를 보면 이 log n은 상수시간 O(1)과 거의 동일하다. 그렇기 때문에 정렬된 배열이라면 아주 유용한 검색 방법이다.

이진 검색이 종료되는 조건

• arr[mid]와 target값이 일치하는 경우
• 검색 범위가 더이상 없는 경우