자바 이진 탐색 완벽 가이드: 개념부터 구현까지

자바로 이진 탐색 알고리즘 작성하기

컴퓨터는 사람처럼 항목을 검색하지 않습니다. 사람은 무언가를 찾을 때 접근 방식을 유연하게 바꿀 수 있지만, 컴퓨터는 특정 항목을 찾는 방법에 대한 명확한 지시가 필요합니다. 바로 이럴 때 표준 알고리즘이 유용하게 쓰입니다.

이진 탐색(binary search)은 대표적인 표준 알고리즘 중 하나로, 정렬된 배열에서 특정 요소를 찾는 데 사용됩니다. 이 가이드에서는 이진 탐색이 무엇인지, 어떻게 작동하는지, 그리고 자바로 어떻게 구현하는지 살펴보겠습니다. 재귀(recursive) 방식과 반복(iterative) 방식 두 가지 예제를 모두 다룰 예정입니다.

그럼 시작해 보겠습니다!

이진 탐색이란?

이진 탐색은 정렬된 배열에서 특정 요소의 위치를 찾아내는 검색 알고리즘입니다.

이진 탐색은 먼저 리스트를 반으로 나누는 것부터 시작합니다. 그런 다음 가운데 있는 숫자와 찾고자 하는 숫자를 서로 비교합니다.

찾고자 하는 숫자가 가운데 숫자보다 작다면 리스트의 하위 절반에서 같은 과정을 반복하고, 그렇지 않다면 상위 절반에서 과정을 반복합니다.

이진 탐색은 또 다른 일반적인 검색 방식인 선형 탐색(linear search)보다 효율적입니다. 알고리즘이 항목을 검색할 때마다 탐색 대상 범위가 절반씩 줄어들기 때문입니다.

단, 이진 탐색은 반드시 정렬된 리스트에서만 수행할 수 있습니다. 따라서 리스트가 아직 정렬되어 있지 않다면, 이진 탐색을 실행하기 전에 먼저 정렬 알고리즘으로 정렬해야 합니다.

이진 탐색은 어떻게 작동할까?

이진 탐색은 반복(iterative) 방식과 재귀(recursive) 방식, 두 가지 방법으로 구현할 수 있습니다.

반복적 이진 탐색은 루프(loop)를 사용해 리스트에서 항목을 찾습니다. 재귀적 이진 탐색은 함수가 스스로를 계속 호출하면서 항목을 찾는 방식으로, 분할 정복(divide and conquer) 기법을 활용합니다.

재귀에 대해 더 자세히 알고 싶다면 자바 재귀 관련 가이드를 참고해 보세요.

어떤 방식을 선택하든 이진 탐색의 기본 알고리즘은 동일합니다.

다음 리스트를 살펴보겠습니다:

이 리스트에서 숫자 7을 찾아보겠습니다. 먼저 리스트의 최솟값 위치와 최댓값 위치를 나타내는 두 개의 포인터를 설정합니다:

Low				High
6	7	8	9	10

다음으로 배열의 가운데 요소를 찾아야 합니다. (low + high) / 2 공식을 사용하면 되며, 이 경우 가운데 요소는 8입니다.

알고리즘은 가운데 요소가 찾고자 하는 값과 같은지 비교합니다. 두 숫자가 같다면 검색을 종료할 수 있습니다. 우리가 찾는 숫자는 7이고 8과 같지 않으므로 검색은 계속 진행됩니다.

그다음 알고리즘은 찾고자 하는 숫자가 가운데 숫자보다 큰지 확인합니다. 크다면 low를 middle_number + 1로 설정해 리스트의 상위 절반에서 검색을 다시 시작합니다. 그렇지 않다면 하위 절반에서 검색을 다시 시작합니다.

찾고 있는 7은 가운데 숫자인 8보다 크지 않습니다. 따라서 알고리즘은 리스트의 하위 절반을 탐색하게 되며, 이때 high 값을 middle_number – 1로 설정합니다.

Low	Middle	High
6	7	8	9	10

이제 알고리즘이 검색을 반복합니다. 가운데 숫자 7과 찾고자 하는 숫자를 비교하면, 찾던 값이 바로 7이므로 검색 알고리즘이 종료됩니다. 리스트에서 7의 위치를 성공적으로 찾은 것입니다!

자바로 이진 탐색 구현하기

이론은 충분히 살펴봤으니 이제 실제로 검색을 구현할 차례입니다. 직접 리스트를 검색하는 것과, 그 검색을 자동으로 수행하는 알고리즘을 코드로 작성하는 것은 전혀 다른 문제입니다.

먼저 반복 방식으로 자바 이진 탐색을 구현하는 프로그램부터 작성해 보겠습니다.

반복(iterative) 방식

항목 목록을 검색하는 searchItems라는 함수를 정의해 보겠습니다:

class BinarySearch {
	int searchItems(int array[], int searchingFor, int low, int high) {
		while (low <= high) {
			int middle = low + (high - low) / 2;

			if (array[middle] == searchingFor) {
				return middle;
			} else if (array[middle] < searchingFor) {
				low = middle + 1;
			} else {
				high = middle - 1;
			}
		}
		return -1;
	}
}

이 함수는 이진 탐색을 사용해 항목 목록을 검색합니다.

함수는 네 개의 매개변수를 받습니다: 검색 대상 리스트(array), 찾고자 하는 항목(searchingFor), 최솟값(low), 최댓값(high).

함수 내부에는 while 루프가 선언되어 있으며, low 값이 high 값보다 작거나 같은 동안 계속 실행됩니다.

while 루프는 먼저 가운데 숫자를 계산한 뒤, 해당 위치의 값이 찾고자 하는 값과 일치하는지 확인합니다.

두 값이 같다면 해당 값을 메인 프로그램에 반환합니다. 일치하지 않는다면, 가운데 위치의 값이 찾고자 하는 값보다 작은지 검사하고, 작다면 새로운 low 값을 설정합니다.

그렇지 않다면 새로운 high 값을 설정해 리스트의 상위 절반에서 다시 검색을 진행합니다.

만약 항목을 찾지 못하면 -1을 반환합니다. 이 값은 메인 프로그램에 해당 항목이 리스트에 없다는 사실을 알리는 데 사용됩니다.

아직 메인 프로그램을 작성하지 않았기 때문에 현재 코드는 아무 동작도 하지 않습니다. BinarySearch 클래스의 searchItems() 함수 아래에 다음 코드를 추가해 보세요:

public static void main(String args[]) {
		BinarySearch newSearch = new BinarySearch();

		int listToSearch[] = { 6, 7, 8, 9, 10 };
		int listLength = listToSearch.length;
		int numberToFind = 7;

		int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1);

		if (findNumber != -1) {
			System.out.println(numberToFind + " was found at index position " + findNumber + ".");
		} else {
			System.out.println(numberToFind + " was not found in the list.");
		}
	}

코드를 실행하면 결과는 다음과 같습니다:

7 was found at index position 1.

We've found the position of our number!

메인 프로그램은 BinarySearch 클래스의 인스턴스를 초기화하는 것부터 시작합니다. 이후 프로그램에서 검색을 시작할 때 이 인스턴스를 사용합니다. 그다음 세 개의 변수를 정의합니다:

listToSearch: 검색 대상 리스트
listLength: 리스트의 길이
numberToFind: 리스트에서 찾고자 하는 숫자

변수를 정의한 후, 앞서 선언한 searchItems() 함수를 호출해 리스트에서 숫자를 찾고, 반환값을 "findNumber" 변수에 저장합니다.

findNumber가 -1과 같지 않다면, 즉 숫자를 찾았다면 해당 항목의 인덱스 위치가 콘솔에 출력됩니다. 그렇지 않다면 숫자를 찾지 못했다는 메시지가 콘솔에 출력됩니다.

재귀(recursive) 방식

이진 탐색은 재귀 방식으로도 구현할 수 있습니다. 이는 지정한 항목을 찾을 때까지 스스로를 호출하는 함수를 작성하는 방식입니다.

먼저 이진 탐색을 재귀적으로 수행하는 함수를 정의해 보겠습니다:

class BinarySearch {
	int searchItems(int array[], int searchingFor, int low, int high) {
		if (high >= low) {
			int middle = low + (high - low) / 2;
	
if (array[middle] == searchingFor) {
				return middle;
			} else if (array[middle] < searchingFor) {
				searchItems(array, searchingFor, middle + 1, high);
			} else {
				searchItems(array, searchingFor, low, middle - 1);
			}
		}
		return -1;
	}
}

이 함수는 앞서와는 다른 방식으로 이진 탐색을 구현합니다. while 루프 대신 if문을 사용해 high 값이 low 값보다 크거나 같은지 검사합니다.

조건이 참이면 검색이 시작되고, 거짓이라면 -1을 반환해 프로그램에 해당 항목을 찾지 못했음을 알립니다.

if문 내부에서는 가운데 숫자의 값이 찾고자 하는 값과 같은지 확인하고, 같다면 그 값을 메인 프로그램에 반환합니다.

조건이 참이 아니라면, 프로그램은 가운데 위치의 숫자가 찾고자 하는 값보다 작은지 검사합니다. 작다면 searchItems() 메서드가 다시 실행되지만, 이번에는 low 값이 가운데 숫자보다 1 큰 값으로 설정됩니다. 이를 통해 탐색 대상 항목 수가 절반으로 줄어듭니다.

그렇지 않다면 searchItems()가 다시 실행되며, high 값이 가운데 숫자보다 1 작은 값으로 설정됩니다. 덕분에 검색 범위를 리스트의 왼쪽 절반으로 좁힐 수 있습니다.

코드를 테스트할 때는 앞서 작성한 동일한 메인 함수를 사용할 수 있습니다. 실행 결과를 확인해 보겠습니다:

7 was found at index position 1.

항목이 다시 한번 성공적으로 찾아졌습니다! 이번에는 반복 방식이 아닌 재귀 방식으로 숫자를 찾은 것입니다.

시간 복잡도 분석

이진 탐색 알고리즘의 최선의 경우(best case) 시간 복잡도는 O(1)입니다. 이는 알고리즘이 처음 비교한 항목이 곧 찾고자 하는 항목일 때 발생합니다.

평균 및 최악의 경우 시간 복잡도는 O(log n)입니다. 즉, 대부분의 경우와 최악의 경우 알고리즘 속도는 리스트의 항목 수에 따라 로그적으로 느려집니다.

마무리

이진 탐색은 정렬된 리스트에서 특정 요소의 위치를 찾는 데 사용되는 알고리즘으로, 배열의 특정 구간 가운데 있는 항목과 찾고자 하는 값을 비교하는 방식으로 동작합니다.

이진 탐색은 선형 탐색보다 효율적입니다. 검색이 수행될 때마다 탐색해야 할 값의 범위가 절반씩 줄어들기 때문입니다.

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