검색 알고리즘

선형 검색 (Linear Search)

배열 안에 수많은 문자열로 이루어진 데이터가 있다고 가정했을 때, 우리는 원하는 값을 어떻게 찾을 수 있을까?

제일 직관적인 방법은 처음부터 하나하나 확인하여 일치하는 값이 나올 때까지 찾는 방법일 것이다. 즉, 일치하는 값이 해당 데이터 안에 없다면 배열의 끝까지 가야 알 수 있다는 말이기도 하다. 그리고 이걸 선형 검색이라 한다.

 

자바스크립트에서 이런 동작을 하는 메소드들이 indexOf, includes, find, findIndex이다.

좀 더 내부 동작을 이해하기 위해 코드로 작성하면 이렇다.

function linearSearch(arr, val){
  for (let i=0; i<arr.length; i++) {
      if (arr[i] === val) return i;
  }
	return -1;
}
linearSearch([34,56,1,3], 1)

이렇듯 선형 검색은 배열의 길이가 늘어날 수록 시간도 비례하여 늘어난다. 즉, O(n) 걸린다.

 

이진 검색 (Binary Search)

선형 검색보다 개선된 알고리즘으로, 중간 지점을 설정하여 찾는 데이터가 중간 지점 기준으로 포함되는 분류만 남기고 나머지 반은 버립니다. 다시 중간 지점을 찍어 나누고 버리고를 반복하며 점점 좁혀가는 방식입니다. 곧 분류된 배열을 대상으로만 검색이 이루어지기 때문에 정렬이 되어 있어야 한다. 

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);
    }
    return arr[middle] === elem ? middle : -1;
}

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

코드로 표현하면 이렇다. 시작 요소와 끝 요소, 중간 요소를 담을 변수를 만들어주고, 중간 요소가 찾는 요소와 일치하지 않고 좌측 포인터(start)가 우측 포인터(end)보다 앞에 있는 동안에만 반복문이 실행된다.

즉, 시작 인덱스, 끝 인덱스, 중간 인덱스를 담은 변수들을 만들어주고 시작 인덱스가 끝 인덱스보다 앞에 있는 동안에만 요소를 찾게 되는 것이다. 이진 검색은 평균적으로 O(log n) 걸린다. 반으로 나누는 방식으로 값을 찾는다는 점을 기억하자. 예로들어 배열의 길이가 16인 데이터에서 값을 찾아낸다면 2 * 2 * 2 * 2 즉, 총 4번의 쪼갬으로 원하는 값을 찾을 수 있게 되는 것이다. 이 말은 곧 n의 크기를 두 배로 늘리더라도 한 단계만 더 추가되어 진행될 뿐이라는 말이다. 빅오 그래프를 보면 알듯이 O(log n)은 굉장히 좋다는 걸 알 수 있다. (빠르다)