이진 검색 소개

빠른 개요

2진 검색은 중요한 검색 알고리즘으로 기술 면접과 검색 항목에서 발생할 수 있는 문제에 사용된다.대형 진열에 대해 이 알고리즘은 매우 빠르다.유일한 문제는 정렬 그룹을 통해서만 완성할 수 있다는 것이다.

전화번호부
많은 사람들이 2진 검색을 고려할 때 전화번호부를 통해 검색하는 것을 좋아한다.현재 대다수의 사람들이 단지 휴대전화에서 연락처를 검색하는 것을 감안하면 이 유형은 좀 유행이 지났지만, 나는 이것이 이 개념을 이해하는 좋은 방법이라고 생각한다.
만약 당신이 전화번호부에 성을 찾으려고 한다면, 예를 들면 스미스, 당신은 어떻게 할 것입니까?대다수의 사람들은 우선 그들이 가능하다고 생각하는 이름으로 넘어갈 것이다. 이것은 아마도 약간의 절반일 것이다.그리고 나서 그들은 그들이 뒤집은 페이지의 이름을 검사할 것이다.만약 당신이 성이 P로 시작하는 페이지를 뒤졌다고 가정해 보세요. P가 s에 있기 전에, 당신은 지금 전화번호부의 뒷부분을 검사해야 한다는 것을 알게 될 것입니다.따라서 스미스가 이 페이지에 없는 것을 알고 있기 때문에, 전화번호부의 모든 이름을 처음부터 삭제할 수 있습니다.

이 과정을 반복하여 전화번호부 나머지 부분의 절반가량에 점을 검색하고, 검색할 이름과 대응하는 페이지를 찾을 때까지 이 이름들을 목표 이름인 스미스와 비교할 수 있다.
이것은 2진 검색의 작업 원리와 매우 비슷하며, 왜 그것이 각 원소를 검색하는 것보다 훨씬 빠른지 설명한다.데이터가 이미 정렬되었기 때문에, 우리는 목표 값이 어디에 있는지 더욱 잘 추측할 수 있다.

위조 코드 처리

이 알고리즘에 대한 지식이 있으면 우리는 위조 코드를 연구하고 우리의 알고리즘이 어떻게 작동해야 하는지 이해할 수 있다.가령 우리가 수조에서 목표치5를 찾는다면: [0, 1, 2, 3, 5, 7, 8].
우리는 함수에 두 개의 매개 변수, 하나의 정렬 수조와 하나의 목표 값을 포함해서 수조에서 찾아야 한다는 것을 안다.패턴 중간에 있는 요소는 항상 확인하고 대상과 비교합니다.만약 일치하는 항목을 찾지 못한다면, 우리는 수조의 새로운 부분, 즉 중간 이후나 중간 이전의 부분을 보아야 한다는 것을 안다.
수조의 중간 위치를 찾는 좋은 방법은 평균값을 사용하는 것이다.평균값을 찾기 위해서는 현재 "조사"중인 그룹 부분의 좌우 양측을 가리키는 지침이 필요합니다우리는 바늘을 함께 넣고 그것을 둘로 나누어야 한다.이런 상황에서 우리는 색인을 우리가 보고 있는 그룹 부분의 맨 왼쪽과 맨 오른쪽 위치의 색인에 저장할 것이다.
다음에 일치하는 항목을 찾을 때까지 그룹의 다른 부분을 계속 볼 수 있도록 순환을 만들 것입니다.모든 순환에 대해 우리는 우리가 보고 있는 그룹 부분의 중간 인덱스를 계산하고 이 인덱스의 값과 목표 값을 비교할 것이다.중간 값이 목표와 일치한다면, 중간 값의 인덱스를 되돌려줍니다.중간 값이 목표 값보다 작으면 왼쪽 포인터를 현재 중간 값 위에 있는 포인터로 설정하여 그룹의 현재 역할 영역의 뒷부분을 보십시오.중간 값이 대상 값보다 크면 오른쪽 포인터를 중간 색인 아래의 포인터로 설정하여 그룹의 현재 역할 영역의 앞부분을 보십시오.그리고 우리는 다시 순환을 실행할 것이다.
전체 그룹을 검색한 후에 일치하는 항목을 찾을 수 없다면, 목표 값을 찾지 못한 색인을 표시하기 위해 -1로 돌아갑니다.
다음은 우리가 현재 파악하고 있는 위조 코드들입니다.

function binarySearch(sortedArray, targetValue) {
  //set leftSide to beginning of array at first
  let leftSide = 0
  //set rightSide to end of array at first so the entire array is in scope
  let rightSide = endOfArray

  while (targetNotFound) {
    // average the left and right pointer to find middle. Will need to round this number to get an integer
    let middle = average(left, right)

    if (targetValue === valueAtMiddleIndex) {
      return middle
    } else if (valueAtMiddleIndex < targetValue) {
      leftSide = middle + 1
    } else if (valueAtMiddleIndex > targetValue) {
      rightSide = middle - 1
    }
  }
  // if target value can't be found in array
  return -1
}

테스트 용례로 코드를 찾아보자.

우리는 [0, 1, 2, 3, 5, 7, 8]부터 검색 중5

leftSide는 0 에서 초기화됩니다.rightSide 에서 초기화됩니다.

제1회:

6 에서 초기화

인덱스middle에 있는 요소는 3

여부3 = = 3?아니오, 목표보다 작아요.

3 현재 = 3+1=5

제2회:

스토리지의 이 부분을 살펴보겠습니다. leftSide

4 현재=(4+6)/2=[5, 7, 8]

인덱스middle에 있는 요소는 5

여부5 = = 7?아니오, 목표보다 커요.

7 현재 = 5-1= 5

제3회:

지금 우리는 이 부분만 본다. rightSide

4 현재=(4+4)/2=[5]

인덱스middle에 있는 요소는 4

없음4 = 5.맞다

반환5, 여기서 = 5

얘가 작용했어!

질문 하나
너는 위조 코드에 문제가 있는 것을 보았니?
만약 순환이 어떤 상황에서 영원히 실행될 수 있다고 생각한다면, 당신은 옳습니다.현재 코드에서, 목표 값을 찾을 때만 순환을 멈추지만, 만약 우리가 그것을 찾지 못한다면, 순환은 영원히 계속될 것이다.
단락의 이 순환의 좋은 방법은 왼쪽 바늘이 오른쪽 바늘을 영원히 넘지 않도록 확보하는 것이다.즉, 만약 수조가 다른 검사할 값으로 내려가고, 이 값이 우리의 목표 값과 같지 않으면, 우리는 순환을 종료합니다.다음은 우리가 업데이트한 위조 코드입니다.

function binarySearch(sortedArray, targetValue) {
  //set leftSide to beginning of array at first
  let leftSide = 0
  //set rightSide to end of array at first so the entire array is in scope
  let rightSide = endOfArray

  // exit loop if left pointer goes past rightPointer. I removed the targetNotFound condition since the return statement within the loop already handles this.
  while (leftSide <= rightSide) {
    // average the left and right pointer to find middle. Will need to round this number to get an integer
    let middle = average(left, right)

    if (targetValue === valueAtMiddleIndex) {
      return middle
    } else if (valueAtMiddleIndex < targetValue) {
      leftSide = middle + 1
    } else if (valueAtMiddleIndex > targetValue) {
      rightSide = middle - 1
    }
  }
  // if target value can't be found in array
  return -1
}

이전과 같은 수조를 사용하여 위조 코드를 훑어보도록 하겠습니다. 새로운 목표 값은 middle 입니다.

우리는 4부터 검색 중4

[0, 1, 2, 3, 5, 7, 8]는 4 에서 초기화됩니다.leftSide 에서 초기화됩니다.

첫 번째 순환, 좌측0rightSide우측6:

0 에서 초기화

인덱스<=에 있는 요소는 6

여부middle = = 3?아니오, 목표보다 작아요.

3 현재 = 3+1=3

왼쪽 3 4 오른쪽 leftSide 때문에 두 번째 순환:

스토리지의 이 부분을 살펴보겠습니다. 4

4 현재=(4+6)/2=<=

인덱스6에 있는 요소는 [5, 7, 8]

여부middle = = 5?아니오, 목표보다 커요.

5 현재 = 5-1= 7

왼쪽 7 4 오른쪽 rightSide 때문에 세 번째 순환:

지금 우리는 이 부분만 본다. 4

4 현재=(4+4)/2=<=

인덱스4에 있는 요소는 [5]

없음middle = 4.아니오, 목표보다 커요.

4 현재 = 4-1=5

while 순환을 종료합니다. 좌측(5이 아니기 때문에4우측(rightSide

반환3

얘가 작용했어!
이 위조 코드는 이미 진실에 매우 가깝지만, 계속하기 전에 작업할 수 있는 JavaScript 함수를 얻을 것을 요구합니다.이것은 gif입니다. 이렇게 하면 당신은 내 아래의 코드를 훔쳐보지 않을 것입니다.

나의 2진 검색 실현

다음은 JavaScript를 사용하여 이 알고리즘을 구현하는 과정입니다.

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

  // I chose to initialize these variables outside the loop
  let middle;
  // currentElem will be the element that is at the middle index
  let currentElem;

  while (right >= left) {
      // Math.floor() will round the decimal down to the nearest integer
      middle = Math.floor((left + right) / 2)

      currentElem = sortedArr[middle];

      if (currentElem === value) {
          return middle;
      } else if (currentElem < value) {
          left = middle + 1;
      } else if (currentElem > value) {
          right = middle - 1;
      }
  }
  return -1;
}

2진 검색의 큰 O

큰 O의 최악의 경우 성능은 O(대수 n)인데 이것은 매우 빠르다.원근법의 경우 대부분의 JavaScript 내장 검색 방법(예: 4은 선형 검색을 사용하기 때문에 O(n)가 있는 time complexity입니다.

적지 않은 진열에 대해 이진 검색은 선형 검색보다 훨씬 빠르다.패턴이 작으면 선형 검색보다 실행 속도가 빠르지 않을 수 있습니다.내가 본 2진 검색의 유일한 단점은 데이터를 정렬해야 한다는 것이다.

건배!

읽어주셔서 감사합니다.나는 내가 오늘 너에게 새로운 것을 가르쳐 줄 수 있기를 바란다. 나는 모든 사람들이 즐겁고 안전한 주말을 보내기를 바란다.

리소스

JavaScript Algorithms and Data Structures Masterclass by Colt Steele

Time Complexity Chart