Searching Algorithms

JavaScript 문법을 활용한 검색 방법에 대해 알아봅시다. 선형 검색, 이진 검색과 더해 문자열 검색을 모두 JavaScript를 활용하여 구현해보도록 하겠습니다.

1. 선형 검색

linearSearch([10, 15, 20, 25, 30], 15); // 1
linearSearch([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], 4); // 5
linearSearch([100], 100); // 0
linearSearch([1, 2, 3, 4, 5], 6); // -1
linearSearch([100], 200); // -1

선형 검색은 앞에서부터 하나하나씩 검색하는 방식입니다. 이러한 이유로 선형 검색이라 불리며, 선형 검색의 Big O는 Best는 한번에 찾는 경우의 O(1), Worst는 가장 마지막에 찾게 되는 O(n)입니다. Big O의 개념에선 아시다시피 평균값이 가장 중요하며 이는 O(n)입니다.

그렇다면 선형 검색은 코드로는 어떠한 방식으로 구현할 수 있을까요?

linearSearch

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

for 반복문을 통해 선형 검색은 쉽게 구현이 가능합니다. i라는 변수의 값이 for를 통해 자동으로 하나씩 증가하기 때문에 i를 반환하는 값이 찾길 원하는 배열의 값의 인덱스값이 됩니다.

2. 이진 검색

binarySearch([1, 2, 3, 4, 5], 2); // 1
binarySearch([1, 2, 3, 4, 5], 5); // 4
binarySearch([1, 2, 3, 4, 5], 6); // -1

이번에는 이진 검색에 대해 알아봅시다. 결과값은 선형 검색과 마찬가지로 배열 내 검색하는 대상의 인덱스 값을 반환하는 알고리즘입니다. 그러나 이진 검색은 선형 검색보다 효율적으로 값을 탐색할 수 있도록 합니다.

먼저 배열 내의 중간값을 구합니다. 그리고 이 배열의 중간값과 검색하는 값을 비교합니다. 당연하게도 두 값이 같다면 해당 값의 인덱스를 반환하면 끝이 납니다.

그러나 이 두 값을 비교하였을 때, 예를 들어 첫 번째의 예시처럼 중간값(3)이 찾으려는 값(2)보다 크다면 중간값을 포함한 뒤의 모든 값을 제외합니다.

그리고 반대로 두 번째의 예시처럼 중간값(3)이 찾으려는 값(5)보다 작다면, 중간값을 포함한 앞의 모든 값을 제외하면 됩니다. 이러한 방식으로 이진 검색은 진행이 됩니다. 이를 반복하면 값을 찾거나 혹은 찾지 못하여 -1을 반환할 수 있습니다.

그렇다면 이를 코드로 구현해보도록 하겠습니다.

binarySearch

function binarySearch(arr, val) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let middle = Math.floor((start + end) / 2);
    if (arr[middle] === val) {
      return middle;
    } else if (arr[middle] > val) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return -1;
}

이진 검색에서 가장 중요한 부분은 중간값을 정해야하는 것입니다. 이를 위해서는 처음값과 마지막값을 알아야합니다. 이것이 위 코드에서는 left와 right로 표현하였습니다.

while(left <= right)

그리고 반복문을 통해 검색을 진행하도록 합니다. while은 참이 될 동안 계속해서 반복하게 되는 반복문으로 해당 코드에서는 left와 right의 값을 변화시키기 때문에 left의 값이 right 값보다 작거나 같은 경우에서 계속해서 반복하여 검색할 수 있도록 합니다.

그리고 중간값을 변수에 저장합니다. 이후 중간값을 기준으로 검색하는 값과 계속해서 비교하며 이진 검색을 진행하도록 합니다. 먼저, 중간값과 검색하는 값이 같다면, middle에 저장해둔 변수의 값이 index이므로 이를 반환하여 줍니다.

그리고 본격적으로 중간값과 검색하는 값이 다른 경우를 살펴보겠습니다.

[1, 2, ⓷, 4, 5]
중간값: 3, 찾는값: 2

[1, 2, ⓷, 4, 5]

이처럼 중간값이 찾으려는 값보다 큰 경우, 예시로는 첫 번째의 예시가 되겠습니다. 이러한 경우는 위에서 언급했던 것처럼 3, 4, 5를 지워주면 left와 right이 각각 1과 2가 되어 다시 검색을 진행하게 되는 것을 이진 검색이라고 합니다.

이를 코드로 구현하게 되면 어떻게 될까요? 바로 아래와 같이 작성할 수 있습니다.

else if (arr[middle] > val) {
  right = middle - 1;
}

right의 값을 중간값이었던 2에서 1을 뺀 1의 값을 입력하는 것입니다. 그렇다면 반대의 경우는 쉽게 예상 가능한 것처럼 left에 middle + 1을 넣어주면 됩니다. 이렇게 이진 검색의 코드 구현에 대해 알아봤습니다.

그렇다면, 이진 검색의 평균 시간 복잡도는 어떻게 될까요? 여기서 바로 O(log n)이 등장합니다. 이진 검색의 경우 16개의 배열 요소가 있다면, 최대 4단계로 끝나게 됩니다. 그리고 32개의 요소라면 최대 5단계에서 검색을 마치게 됩니다. 이러한 계산 방식에서 log가 사용되게 되는 것입니다.

이진 검색은 Big O의 개념에서 O(log n)를 가장 쉽게 확인할 수 있는 알고리즘이라고 할 수 있습니다. 그리고 이 개념은 이후에도 계속해서 나오게 되므로 매우 중요합니다.