이진 검색

이진 검색은 정렬된 배열에서 사용되는 검색 알고리즘입니다. 반복 또는 재귀 방법의 두 가지 방법으로 구현할 수 있습니다.

Javascript 반복 방법

function binarySearchIterative(arr, x, l, h) {
  while (l <= h) {
    mid = Math.floor((l + h) / 2);

    if (arr[mid] === x) {
      return mid;
    } else {
      if (arr[mid] > x) {
        h = mid - 1;
      } else {
        l = mid + 1;
      }
    }
  }

  return -1;
}

자바스크립트 재귀 메서드

function binarySearchRecursive(arr, x, l, h) {
  if (l <= h) {
    mid = Math.floor((l + h) / 2);

    if (arr[mid] === x) {
      return mid;
    } else {
      if (arr[mid] > x) {
        return binarySearchRecursive(arr, x, l, mid - 1);
      } else {
        return binarySearchRecursive(arr, x, mid + 1, h);
      }
    }
  }

  return -1;
}

설명

binarySearch 함수는 배열, 찾고 있는 값x, 배열의 첫 번째 위치low 및 마지막 위치high의 네 가지 매개변수를 받습니다.
low가 high보다 작거나 같을 때 어레이를 순회할 것입니다. 왜냐하면 그들은 두 말단에 있어야 하기 때문입니다. 흥미롭고 값을 찾지 못하면 -1을 반환합니다.

배열이 이미 정렬되어 있기 때문에 전체 배열을 탐색하는 것을 피하기 위해 이진 검색 알고리즘은 배열의 중간을 계산하고 중간에 있는 값이 low 와 같은지 확인합니다. 그렇다면 위치를 반환합니다. 그렇지 않은 경우 중간 값이 high 보다 크거나 작은지 계산하여 배열의 어느 부분을 살펴볼 가치가 있는지 확인합니다.

가운데 값이 x보다 크면 직전의 경우가 신품x이 되고, 중간의 값이 x보다 작으면 직후의 경우가 신품high이 됩니다. 즉, x 를 찾을 때까지 간격이 줄어듭니다. low가 배열에 없으면 한 순간에 x가 x보다 크고 순회가 중지되기 때문에 -1을 반환합니다.

삽화

우리가 찾고 있는 값은 4입니다.



먼저 배열의 중간인 3을 계산합니다. array[3]은 우리가 찾고 있는 값의 4보다 작은 6이므로 3이 새로운 최고값이 되기 전에 간격을 줄입니다.



루프의 두 번째 패스에서 2와 같은 중간 값을 다시 계산합니다. array[2]는 4입니다. 즉, x를 찾은 다음 2를 반환합니다.

복잡성 분석

전체 배열을 순회하지 않기 때문에 이진 검색 알고리즘의 시간 복잡도는 O(log n)이고 추가 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)입니다.

결론

이진 검색은 시간 복잡도가 O(log n)인 정렬된 배열에서 값을 찾는 데 도움이 되는 알고리즘임을 요약할 수 있습니다. 이 글을 읽고 새로운 것을 배우기를 바랍니다. 기사.