자바스크립트 이진 탐색 완벽 가이드: 개념부터 반복·재귀 구현까지

자바스크립트로 이진 탐색 코드 작성하기

탐색 알고리즘은 프로그래머에게 없어서는 안 될 도구입니다. 수십, 수백, 수천 개의 항목으로 이루어진 데이터 집합에서도 원하는 항목을 손쉽게 찾을 수 있게 해주기 때문입니다.

가장 널리 쓰이는 탐색 방식 중 하나가 바로 이진 탐색(binary search)입니다. 이진 탐색은 배열에서 특정 항목을 빠르게 찾아내며, 항목을 하나 확인할 때마다 남은 탐색 범위를 절반으로 줄여 나갑니다.

이 가이드에서는 이진 탐색이 무엇이고 어떻게 동작하는지 살펴본 뒤, 반복(iterative) 방식과 재귀(recursive) 방식, 두 가지 접근법으로 직접 구현해 보겠습니다.

지금부터 자바스크립트로 이진 탐색 알고리즘을 만들어 봅시다!

이진 탐색이란?

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

배열의 중간 지점에서 시작해, 중간값이 찾으려는 숫자보다 작은지, 같은지, 큰지를 확인합니다.

찾으려는 숫자가 더 작다면 알고리즘은 작은 숫자들이 모여 있는 왼쪽 절반을 계속 탐색하고, 더 크다면 오른쪽 절반에 집중합니다. 즉, 이진 탐색은 반드시 정렬된 목록에서만 동작합니다.

이진 탐색은 선형 탐색(linear search)보다 효율적입니다. 탐색을 한 번 진행할 때마다 남은 항목 수가 절반으로 줄어들기 때문입니다.

이진 탐색 사용 방법

이진 탐색은 익숙해지면 아주 쉽게 이해할 수 있습니다.

알고리즘을 구현하기 전에, 단계별로 과정을 먼저 짚어 보겠습니다. 정렬된 다음 목록에서 숫자 "9"를 찾는다고 가정해 봅시다:

먼저 중간값을 찾아 변수에 할당해야 합니다. 중간값은 첫 번째 숫자와 마지막 숫자를 더한 뒤 2로 나누어 구하며, 여기서는 "middle"이라는 변수로 부르겠습니다:

중간값은 8입니다. 이제 중간값과 찾으려는 숫자를 비교합니다. 두 값이 같다면 탐색은 종료됩니다.

이 예제에서 8은 9와 같지 않으므로 탐색은 계속됩니다.

다음으로 중간값이 9보다 큰지 확인합니다. 그렇지 않습니다.

이는 찾으려는 숫자가 중간값 뒤쪽에 있다는 뜻입니다. 정렬된 목록에서 9는 8보다 크기 때문입니다. 따라서 시작 지점(start)을 중간값 위치로 옮깁니다. 찾으려는 숫자가 중간값보다 앞에 있을 가능성이 없기 때문입니다.

반대로 찾으려는 숫자가 더 작다면 끝 지점(end)을 중간값으로 설정해 목록의 아래쪽 절반에 집중하면 됩니다.

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

다시 중간값을 찾으면 9입니다. 이 값을 찾으려는 숫자와 비교하면 서로 일치합니다.

즉, 탐색을 종료할 수 있습니다. 목록에서 숫자 9를 성공적으로 찾았습니다!

자바스크립트로 이진 탐색 구현하기

이진 탐색은 반복(iterative) 방식 또는 재귀(recursive) 방식으로 구현할 수 있습니다.

반복문을 사용한 이진 탐색

반복 방식의 이진 탐색은 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;
}

먼저 start와 end라는 두 변수를 정의합니다. 이 변수들은 탐색 범위의 최솟값과 최댓값을 추적합니다. while 루프는 start가 end보다 커질 때까지 실행되며, 매번 start와 end 사이의 중간 인덱스를 계산합니다.

찾으려는 숫자가 중간값과 같다면 해당 인덱스를 메인 프로그램에 반환합니다. 찾으려는 숫자가 더 크다면 start를 middle + 1로 설정합니다. 이러한 비교는 if 문으로 처리합니다.

그 외의 경우, 즉 찾으려는 숫자가 중간값보다 작다면 end를 middle - 1로 설정합니다. while 루프가 모두 실행된 후에도 숫자를 찾지 못했다면 -1을 반환하는데, 이를 기저 조건(base condition)이라고 부릅니다. 메인 프로그램에서는 반환값이 -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.

탐색이 성공적으로 완료되었다는 의미입니다!

재귀를 사용한 이진 탐색

재귀 방식의 이진 탐색은 반복 방식보다 더 우아하다는 평가를 받습니다. 이진 탐색은 목록에 대해 동일한 연산을 계속 반복하기 때문인데, 이런 동작은 재귀 알고리즘으로 자연스럽게 구현할 수 있습니다.

새 자바스크립트 파일을 열고 다음 코드를 붙여 넣어 보세요:

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 문은 start가 end보다 큰지 확인합니다. 그렇다면 지정한 목록에서 항목을 찾지 못한 것이므로 메인 프로그램에 -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.

이진 탐색이 성공했습니다! 내부적으로 사용되는 알고리즘은 반복 방식과 동일합니다. 차이점이라면, 함수가 스스로를 호출하며 항목을 찾거나 목록 전체를 탐색할 때까지(먼저 도달하는 조건까지) 탐색을 진행한다는 점입니다.

마무리

이진 탐색을 활용하면 목록에서 항목을 쉽게 찾을 수 있습니다. 탐색이 실행될 때마다 남은 항목 수가 절반으로 줄어들기 때문에 선형 탐색보다 훨씬 효율적입니다.

이제 여러분도 전문가처럼 자바스크립트로 이진 탐색을 구현할 준비가 되었습니다!