이진 검색

개발 초보 2022. 6. 26. 15:15

이진 검색 알아보기

이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 일렬로 나열된 배열에서 특정 값을 검색할 때, 배열의 중앙에 위치한 요소부터 검색을 시작한다. 예로 요소가 오름차순으로 정렬된 데이터에서 6을 찾으려는 경우다.

1	2	3	4	6	8	10	//a[7] 배열

위 배열에서 6을 탐색할 때, 중앙에 위치한 a[3], 4부터 탐색한다. a[3]는 찾으려는 값보다 작으므로 탐색은 a[3]의 오른쪽만 진행하면 된다.

6	8	10

a[3] 이하, 즉 4보다 왼쪽에 있는 요소들을 제하고 오른쪽에서 탐색을 진행한다. 다시 중앙인 a[5], 8부터 검색을 시작한다. a[5]가 찾으려는 값보다 크므로 a[5]의 왼쪽으로 진행한다. a[4], 6을 발견했다. 검색을 종료한다.

검색 범위 맨 앞의 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라 지정한다. 검색을 시작할 때 pl은 0, pr은 n - 1, pc는 (n - 1) / 2다.

a[pc] < key 일 때

a[pl] ~ a[pc]는 key보다 작은 것이므로 검색 대상에서 제외한다. 검색 범위를 중앙 요소 a[pc]보다 뒤쪽인 a[pc + 1] ~ a[pr]로 좁힌다. 이를 위해 pl값을 pc + 1로 업데이트한다.

a[pc] > key 일 때

a[pc] ~ a[pr]은 key보다 큰 것이므로 검색 대상에서 제외한다. 검색 범위를 중앙 요소 a[pc]보다 앞쪽인 a[pl] ~ a[pc - 1]로 좁힌다. 이를 위해 pr값을 pc - 1로 업데이트한다.

복잡도 구하기

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라 한다. 복잡도는 아래 두 가지 요소를 갖고 있다.

- 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것
- 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

선형 검색의 시간 복잡도

아래 선형 검색 메서드를 바탕으로 시간 복잡도를 살펴보자.

이진 검색의 시간 복잡도

Arrays.binarySearch에 의한 이진 검색

자바는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다. java.util.Arrays 클래스의 binarySearch 메서드가 그것이다. 이 메서드는 아래 같은 장점이 있다.

- 이진 검색 메서드를 직접 작성할 필요가 없다.
- 배열 요소의 자료형과 관계없이 검색할 수 있다.

binarySearch 메서드는 오름차순으로 정렬된 배열 a를 가정하고 값이 key인 요소를 이진 검색한다. 또 자료형과 관계없이 검색할 수 있게 자료형에 따라 9가지 방법으로 오버로딩되어 있다.

검색에 성공한 경우

key와 일치하는 요소의 인덱스를 반환한다. key와 일치하는 요소가 여러 개 있으면 어느 요소의 인덱스를 반환하는지는 미정이다. 즉, 맨 앞의 요소의 인덱스를 반환한다는 보증은 없다.

검색에 실패한 경우

검색에 실패했을 때는 '배열 안데 key가 있어야 할 위치(삽입 포인트)를 추정할 수 있는 값'을 반환한다. 삽입 포인트를 x라 하면 반환값은 (-x) - 1이다. 검색하기 위해 지정한 key보다 큰 요소 중 첫 번째 요소의 인덱스다. 만약 배열의 모든 요소가 key보다 작다면 배열의 길이를 삽입 포인트로 정한다.

기본 자료형 배열에서 binarySearch 메서드로 검색하기

아래는 int형 배열에서 binarySearch 메서드를 사용해 검색하는 프로그램이다.

객체의 배열에서 검색하기

객체의 배열에서 검색은 아래 메서드들을 사용한다.

A | static int binarySearch(Object[] a, Object key) : 
	자연 정렬(natural ordering)이 된 배열에서 요소의 대소 관계를 판단하고 검색하는 메서드다. 따라서 
   	 정수 배열, 문자열 배열에서 검색할 때 적당하다.

B | static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) : 
	자연 정렬이 아닌 순서로 나열된 배열에서 검색하는 메서드다. 자연 정렬을 논리적으로 갖지 않는 
   	 클래스의 배열에서 검색할 때 알맞다.

A | 자연 정렬이 된 배열에서 검색하기

아래는 자연 정렬에서 대소 관계를 비교하는 메서드를 사용해 검색하는 프로그램이다. 검색 대상 x는 문자열 배열이다. 문자열을 ky에 입력하고 배열 x와 키값 ky를 binarySearch 메서드에 전달하면 검색할 수 있다.

B | 자연 정렬이 되지 않은 배열에서 검색하기

자연 정렬이 되지 않은 배열에서의 검색은 제네릭 메서드(generic method)를 사용한다. 제네릭으로 구현한 아래 메서드에서 첫 번째 매개변수 a는 검색 대상, 두 번째 매개변수 key는 키값이다. 제네릭 메서드는 자료형에 구애받지 않기에 매개변수로 전달하는 자료형은 Integer, String, 신체검사 데이토용 클래스 PhyscData 등 어떤 것을 전달해도 상관없다.

다만 배열 요소가 어떤 순서로 나열되어 있는지, 각 요소의 대소 관계를 어떻게 판단할지 등은 binarySearch 메서드에 알려줘야 한다. 이 정보는 세 번째 매개변수 c에 전달된다.

static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

세 번째 매개변수 c에 comparator를 전달한다. 객체의 대소 관계를 판단하는 comparator를 사용자가 직접 구현하려면 Comparator 인터페이스를 구현한 클래스를 정의하고 그 클래스형의 인스턴스를 생성해야 한다. 그런 후 매개변수로 전달된 두 객체의 대소 관계를 비교해 그 결과를 아래 값으로 반환하는 compare 메서드를 구현하면 된다.

- 첫 번째 인수가 더 크면 양수
- 첫 번째 인수가 더 작으면 음수
- 첫 번째 인수와 두 번째 인수가 같으면 0

따라서 클래스 X에 대한 comparator는 아래처럼 정의할 수 있다.

class X {
	public static final Comparator<T> COMPARATOR = new Comp();
    
    private static class Comp implements Comparator<T> {
    	public int compare(T d1, T d2) {
        	if(d1 > d2)
            	return 1;
            else if(d1 < d2)
            	return -1;
            else
            	return 0;
        }
    }
}

아래는 키의 순서로 정렬된 신체검사 데이터의 배열에서 특정한 사람의 키를 검색하는 프로그램이다.

참고 서적 :