바이너리 검색 JavaScript:가이드

자바스크립트에서 이진 검색을 코딩하는 방법

알고리즘을 검색하면 프로그래머로서의 삶이 훨씬 쉬워집니다. 이렇게 하면 수십, 수백 또는 수천 개의 항목으로 구성된 데이터 세트 내에서 특정 항목을 쉽게 찾을 수 있습니다.

가장 인기 있는 검색 형식 중 하나는 이진 검색입니다. 이 검색은 배열에서 항목을 빠르게 찾습니다. 항목을 검색할 때마다 검색할 남아 있는 항목 수가 절반으로 줄어듭니다.

이 가이드에서는 바이너리 검색이 무엇이고 어떻게 작동하는지에 대해 이야기할 것입니다. 그런 다음 반복 및 재귀라는 두 가지 다른 접근 방식을 사용하여 이진 검색을 구현합니다.

JavaScript로 바이너리 검색 알고리즘을 만들어 봅시다!

이진 검색이란 무엇입니까?

이진 검색은 정렬된 배열에서 항목을 검색하는 컴퓨터 과학 알고리즘입니다.

배열의 중간에서 시작하여 중간 항목이 검색하려는 숫자보다 작은지, 같은지 또는 큰지 확인합니다.

숫자가 더 작으면 알고리즘은 더 작은 숫자가 있는 배열의 왼쪽 절반에서 계속 검색한다는 것을 알고 있습니다. 숫자가 더 크면 알고리즘은 배열의 오른쪽 절반에 초점을 맞춥니다. 이진 검색은 정렬된 목록에서만 작동합니다.

이진 검색은 선형 검색보다 더 효율적입니다. 검색할 때마다 목록에서 검색할 수 있는 항목의 수가 절반으로 줄어들기 때문입니다.

참가자의 81%는 부트캠프에 참석한 후 기술 직업 전망에 대해 더 자신감을 느꼈다고 말했습니다. 지금 부트캠프에 참여하십시오.

부트캠프 졸업생은 부트캠프 시작부터 첫 직장을 찾는 데까지 6개월도 채 걸리지 않았습니다.

이진 검색을 사용하는 방법

이진 검색은 일단 익숙해지면 이해하기 쉽습니다.

이진 검색 알고리즘을 구현하기 전에 단계별로 살펴보겠습니다. 목록에서 숫자 "9"를 찾을 것입니다. 정렬된 목록으로 시작하겠습니다.

먼저 중간 숫자를 찾아 변수에 할당해야 합니다. 이것은 첫 번째 숫자와 마지막 숫자의 합을 계산하고 2로 나누어 구합니다. 이 변수를 "중간"이라고 부를 것입니다.

시작		중간		종료
2	6	8	9	10

8은 중간 숫자입니다. 그런 다음 중간 숫자를 우리가 찾고 있는 숫자와 비교할 수 있습니다. 중간 숫자가 우리가 찾고 있는 숫자와 같으면 탐색이 중지될 수 있습니다.

이 예에서 8은 9와 같지 않습니다. 검색은 계속됩니다.

다음으로 중간 숫자가 9보다 큰지 비교해야 합니다. 그렇지 않습니다.

이것은 우리가 검색하는 숫자가 중간 숫자 뒤에 있어야 함을 알려줍니다. 9는 정렬된 목록에서 8보다 큽니다. 우리는 시작 숫자를 중간 숫자와 같도록 설정할 것입니다. 이것은 우리가 찾고 있는 숫자가 중간 숫자 앞에 오지 않는다는 것을 알고 있기 때문입니다.

검색하는 숫자가 더 작으면 끝 숫자를 중간 숫자와 같도록 설정합니다. 숫자가 중간 숫자보다 작기 때문에 목록의 아래쪽 절반에 검색을 집중할 수 있습니다.

9가 8보다 크므로 이진 검색이 목록의 위쪽 절반에서 다시 반복됩니다.

		시작	중간	종료
2	6	8	9	10

우리는 중간 숫자를 다시 찾습니다. 이것은 9입니다. 9를 우리가 찾고 있는 숫자와 비교할 수 있습니다. 9는 우리가 찾고 있는 숫자와 같습니다.

이는 검색을 중지할 수 있음을 의미합니다. 목록에서 9번을 성공적으로 찾았습니다!

자바스크립트에서 이진 검색을 구현하는 방법

이진 검색은 반복 또는 재귀 접근 방식을 사용하여 구현할 수 있습니다.

반복 이진 검색

반복 이진 검색은 while 루프를 사용하여 목록에서 항목을 찾습니다. 이 루프는 목록에서 항목을 찾거나 목록을 검색할 때까지 실행됩니다.

이진 검색을 수행하는 함수를 작성하여 시작하겠습니다.

function binarySearch(array, numberToFind) {
	let start = 0;
	let end = array.length - 1;

	while (start <= end) {
		let middle = Math.floor((start + end) / 2);

		if (array[middle] === numberToFind) {
			return middle;
		} else if (array[middle] < numberToFind) {
			start = middle + 1;
		} else {
			end = middle - 1;
		}
	}

	return -1;
}

시작과 끝이라는 두 가지 변수를 정의하는 것으로 시작합니다. 이것들은 우리가 검색하는 가장 높은 값과 가장 낮은 값을 추적합니다. 시작 번호가 끝 번호보다 클 때까지 실행되는 while 루프를 사용합니다. 이 루프는 목록에서 시작과 끝 사이의 중간 숫자를 계산합니다.

찾고 있는 숫자가 중간 숫자와 같으면 중간 숫자가 주 프로그램으로 반환됩니다. 숫자가 더 작으면 시작 값은 중간 숫자에 1을 더한 값과 같도록 설정됩니다. 이러한 비교는 if 문을 사용하여 수행됩니다.

그렇지 않으면 끝 숫자는 중간 숫자에서 1을 뺀 값과 같도록 설정됩니다. while 루프가 실행된 후 번호를 찾지 못하면 -1이 반환됩니다. 이것을 기본 조건이라고 합니다. 주 프로그램에서 반환된 숫자가 -1인지 확인합니다. 그렇다면 우리 번호를 찾을 수 없다는 의미입니다.

우리의 기능은 아직 작동하지 않습니다. 우리는 그것을 호출하는 메인 프로그램을 작성해야 합니다:

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind);

if (findNumber !== -1) {
	console.log(`${toFind} has been found at position ${findNumber}.`);
} else {
	console.log(`${toFind} has not been found.`);
}

검색할 번호 목록과 목록에서 찾고자 하는 번호를 정의했습니다. 다음으로 binarySearch 함수를 호출했습니다. 이렇게 하면 검색이 수행됩니다. 검색은 -1 또는 검색 중인 항목의 위치를 반환합니다.

-1은 항목을 찾을 수 없음을 나타냅니다. 항목을 찾을 수 없으면 else의 내용이 문이 실행됩니다. 그렇지 않으면 if의 내용 문이 실행됩니다.

코드를 실행해 보겠습니다.

9 has been found at position 3.

이것은 우리의 검색이 성공했음을 알려줍니다!

재귀적 이진 검색

재귀 이진 검색은 반복 검색보다 더 우아한 것으로 간주됩니다. 이는 이진 검색이 목록에서 동일한 작업을 반복해서 수행하기 때문입니다. 이 동작은 재귀 알고리즘을 사용하여 구현할 수 있습니다.

새 JavaScript 파일을 열고 다음 코드를 붙여넣습니다.

function binarySearch(array, numberToFind, start, end) {
	if (start => end) {
		return -1;
	}

	let middle = Math.floor((start + end) / 2);

	if (array[middle] === numberToFind) {
		return middle;
	} else if (array[middle] < numberToFind) {
		return binarySearch(array, numberToFind, middle + 1, end);
	} else {
		return binarySearch(array, numberToFind, start, middle - 1);
	}
}

이 코드는 첫 번째 검색과 동일한 비교를 수행합니다. 중간 숫자가 우리가 검색하는 숫자와 같은지, 크거나 작은지 확인합니다.

함수 시작 시 if 문을 사용하여 시작 번호가 끝 번호보다 큰지 확인했습니다. 그렇다면 우리가 지정한 목록에서 항목을 찾을 수 없음을 의미합니다. 이 경우 주 프로그램에 -1을 반환합니다.

찾고 있는 숫자가 중간 숫자와 같으면 중간 숫자가 메인 프로그램으로 반환됩니다. 찾고 있는 숫자가 중간 숫자보다 크거나 작으면 binarySearch 함수가 다시 실행됩니다. 이것은 항목을 찾을 때까지 계속됩니다.

이 기능을 실행하려면 기본 프로그램을 변경해야 합니다.

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1);
…

"start" 및 "end" 값이라는 두 개의 추가 매개변수를 전달해야 합니다. "start"의 값은 0과 같습니다. "end"의 값은 목록의 길이에서 1을 뺀 것과 같습니다.

코드를 실행하고 어떤 일이 일어나는지 봅시다:

9 has been found at position 3.

바이너리 검색이 성공했습니다! 반복 접근 방식과 동일한 기본 알고리즘을 사용합니다. 차이점은 이진 검색은 항목을 찾을 때까지 또는 목록이 완전히 검색될 때까지 중 먼저 도래하는 때까지 자신을 호출하는 함수를 사용하여 수행된다는 것입니다.

결론

이진 검색을 사용하면 목록에서 항목을 쉽게 찾을 수 있습니다. 검색을 실행할 때마다 목록에서 검색할 수 있는 항목의 수가 절반으로 줄어듭니다. 이것은 선형 검색보다 이진 검색을 더 효율적으로 만듭니다.

이제 전문가처럼 JavaScript에서 바이너리 검색을 구현할 준비가 되었습니다!