JavaScript의 선형 및 이진 검색

이번 주에 저는 Grokking의 Algorithms, 프로그래머 및 기타 호기심 많은 사람들을 위한 그림 가이드를 읽기 시작했습니다. 지금까지는 기술 개념을 이해할 수 있는 방식으로 설명하기 위해 재미있는 그림과 함께 실용적인 예제로 가득 찬 환상적인 읽기였습니다. 이 책의 코드 예제는 Python으로 작성되었습니다. 나는 주로 자바스크립트 개발자이기 때문에 이 책을 통해 내 방식대로 작업하고 내 자바스크립트 코드를 보여줄 것이라고 생각했습니다.

배열을 통한 검색

목록에서 무언가를 찾고 있습니다. 실제로 목록에 있는지 확실하지 않지만 있다면 어디에 있는지 알고 싶습니다. 이 경우 무지개가 있고 특정 색상을 찾고 있습니다.

var rainbow = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];

쉬운 나쁜 선형 방법

"쉬워요! 배열의 각 요소를 반복하고 일치 항목을 반환하겠습니다!"라고 생각할 수 있습니다. 이것은 작동하며 선형 검색이라고 합니다.

function linearSearch(arr, elToFind) {
  for (var i=0; i<arr.length; i++) {
    if (arr[i] == elToFind) {
      return i;
    }
  } return null;
}

linearSearch(rainbow, "green"); // returns 3
linearSearch(rainbow, "white"); // returns null

Buttttttt, (그리고 이것의 크기는 데이터 세트의 크기에 따라 다름) 여기에는 성능 상충 관계가 있습니다. 배열의 일부가 아님을 확인하려면 모든 단일 요소를 반복해야 합니다. 7가지 색상만 이야기할 때 이것은 nbd이지만 수천 또는 수백만 개의 레코드 배열을 살펴보고 있다면 어떨까요? Forget it.

이진 검색

Abinary search는 정렬된 배열을 가져와서 특정 요소를 찾습니다. 요소가 배열에 있는 경우 검색은 요소의 인덱스를 반환합니다. 그렇지 않으면 null을 반환합니다. 배열이 이미 정렬되어 있기 때문에 검색 대상 검색 요소를 배열 중간에 있는 요소와 비교하여 한 번에 검색 범위의 절반을 제거할 수 있습니다. 더 뜨겁고 더 차가운 게임이라고 생각하십시오.

이진 검색으로 Rainbow 예제 재시도

당신과 나는 앞서 언급한 무지개의 ROY G. BIV 순서를 이해하지만, 당신의 브라우저는 Kindergarten으로 가지 않았습니다. Rainbow에서 이진 검색을 수행하려면 (알파벳순으로) 정렬해야 합니다. 다행스럽게도 JavaScript에는 배열에 대한 정렬 방법이 내장되어 있습니다.

var rainbow = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
var sortedRainbow = rainbow.sort(); 
// returns ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];

엄청난! 이제 이진 검색에 전달할 수 있는 것이 있습니다.

function binarySearch(sortedArray, elToFind) {
  var lowIndex = 0;
  var highIndex = sortedArray.length - 1;
  while (lowIndex <= highIndex) {
    var midIndex = Math.floor((lowIndex + highIndex) / 2);
    if (sortedArray[midIndex] == elToFind) {
      return midIndex;
    } else if (sortedArray[midIndex] < elToFind) {
      lowIndex = midIndex + 1;
    } else {
      highIndex = midIndex - 1;
    }
  } return null;
}

var sortedRainbow = ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];
binarySearch(sortedRainbow, "green"); // returns 1
binarySearch(sortedRainbow, "white") // returns null

좋아, 많이 했어. 아니면 당신이 검색 천재이고 그것을 완전히 이해했을 수도 있습니다. 이진 검색을 한 줄씩 살펴보겠습니다.

binarySearch 함수는 sortedArray와 찾고 있는 요소(elToFind)를 받습니다.

검색하는 동안 시작 lowIndex 0과 정렬된 배열의 요소 수 시작 highIndex를 사용하여 검색 중인 범위를 추적하게 됩니다. 검색 시작 시 범위는 전체 배열에 걸쳐 있습니다.

while 루프는 검색이 한 요소로 좁혀질 때까지 실행됩니다.

lowIndex와 highIndex 사이의 요소 인덱스를 찾으려면 이 두 값의 평균을 구합니다(참고: midIndex는 정수여야 하므로 Math.floor를 사용하여 이 값을 내림합니다)

요소를 찾은 경우 인덱스

를 반환합니다.

현재 요소가 검색 중인 요소보다 작은 경우(알파벳순으로 앞), lowIndex를 midIndex보다 하나 더 늘립니다.

현재 요소가 검색 중인 요소보다 크면(알파벳순으로 뒤따름) highIndex를 midIndex보다 1 작은 값으로 줄입니다.

요소가 배열에 없으면 null을 반환합니다

.

다음

이제 두 가지 검색 방법(선형 및 이진)을 살펴보았으므로 서로에 대한 성능을 측정할 방법이 필요합니다. 내 다음 게시물에서는 로그(대수학 2로 후퇴)와 Big O 표기법을 살펴보겠습니다. 계속 지켜봐!