JavaScript에서 이진 검색 알고리즘 작성

컴퓨터 과학에서 검색 알고리즘만큼 자주 사용되는 도구는 거의 없습니다. 우리는 프로그래머와 엔지니어로서 매일 데이터에 의존하여 데이터를 살펴보고 거의 모든 최신 프로그래밍 언어에 어떤 식으로든 내장되어 있습니다.

가장 중요하고 널리 사용되는 검색 알고리즘 중 하나는 이진 검색으로 알려져 있으며 반간 검색, 대수 검색 또는 이진 절단이라고도 합니다. Wikipedia 이진 검색의 기능을 다음과 같이 설명합니다.

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

기본적으로 우리가 하고 있는 것은 루프를 반복할 때마다 검색 중인 배열을 반으로 나누고 해당 중간점을 확인한 다음 대상과 비교하여 배열을 다시 반으로 나누어야 하는지 확인하는 것입니다. 왼쪽이든 오른쪽이든. 그런 다음 왼쪽 및 오른쪽 포인터를 증가 또는 감소시켜 창을 축소합니다. 시각화하기 위해 다음 예를 살펴보겠습니다.

array = [0, 2, 4, 7, 8, 10, 12]
target = 4

         \/ midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
 ^ left              ^ right


   \/ new midpoint, not target
[0, 2, 4, 7, 8, 10, 12]
 ^     ^

      \/ new midpoint, target!
[0, 2, 4, 7, 8, 10, 12]
       ^

이것은 처음에는 약간 이상하게 보일 수 있지만, 생각할수록(그리고 코드에 넣으면) 빠르게 이해될 것입니다.

이진 검색이 작동하는 방식의 핵심은 작업 중인 정수 배열이 정렬되어 있다는 사실을 아는 것입니다. 각 중간점을 대상과 비교하고 오름차순으로 정렬할 때 적절하게 왼쪽 또는 오른쪽에 있을 것이라고 가정하기 때문에 이것은 필수입니다.

이로 인해 이진 검색을 사용할 수 있는 기회가 다소 제한되지만 정렬된 데이터로 작업할 때 사용하는 것이 가장 좋은 검색인 경우가 많습니다. 배열을 반으로 나눈 결과 Binary Search는 O(log n)의 최상의 런타임 복잡성을 가지며, 이는 검색 최적화가 진행되는 한 견고합니다.

구현해야 할 때입니다!

이진 검색 알고리즘을 구현하는 것은 핵심 논리를 이해하는 것과 관련하여 실제로 매우 간단하며 14줄 이하의 코드로 수행할 수 있습니다.

한 줄 한 줄 함께 만들어 봅시다!

먼저 함수와 해당 매개변수를 선언합니다.

function binarySearch(arr, target) {

}

다음으로, 초기 값으로 왼쪽 및 오른쪽 포인터를 정의합니다. 왼쪽 포인터는 배열의 시작 부분에서 시작하고 오른쪽 포인터는 끝에서 시작합니다.

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

이제 함수에 대한 핵심 로직인 while 루프를 추가합니다. 이 while 루프는 왼쪽과 오른쪽 포인터의 값을 비교하고 왼쪽이 오른쪽보다 작거나 같은 한 계속 실행됩니다.

본질적으로 이것은 우리의 창이 "닫힐"때까지 루프가 실행되도록 지시할 것입니다. 즉, 가능한 한 작게 배열을 분해했지만 여전히 대상 값을 찾을 수 없다는 의미입니다. 이 경우 루프 뒤에 반환 값을 추가합니다.

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

  while (left <= right) {

  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

이제 루프에서 작업할 것입니다. 먼저 중간점 변수를 선언하고 그 값을 계산한 다음 값을 반환하고 대상이 발견되면 함수를 종료하는 "기본 사례"를 추가합니다.

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

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

이 버전의 알고리즘에서는 배열에서 찾은 경우 대상 값의 인덱스를 단순히 반환합니다. 이 반환 값은 원하는 대로 변경할 수 있습니다.

마지막으로 중요한 것은 대상이 중간점의 왼쪽 또는 오른쪽에 있는지 확인하고 그에 따라 포인터를 증가 또는 감소시키는 if else 문을 구현할 것입니다.

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

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;

    if (target < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return "Target Not Found"
  // could also return -1, false, undefined, etc
}

그리고 우리는 끝났습니다!

위의 코드는 완성된 알고리즘으로, 적절하다고 판단되는 모든 곳에서 구현할 수 있습니다.

많은 프로그래밍 언어에는 이진 검색이 구문에 내장되어 있거나 더 쉽게 구현할 수 있는 옵션을 제공합니다. 그러나 배열을 더 작은 섹션으로 나누고 값을 비교하여 작동 방식의 핵심 논리를 이해하는 것은 기술 인터뷰 및 설계에 매우 중요합니다. 특정 문제를 해결하기 위한 자체 알고리즘.


여기까지 오셨다면 읽어주셔서 대단히 감사합니다! :) 계속 진행하면서 프로그래머로서 배우고 있는 것들에 대해 더 많은 튜토리얼과 심도 있는 다이빙을 계속할 것입니다.