03_이진 검색(binary search)

- 복잡도: O(log n)

- 전제 조건: 데이터가 키 값으로 이미 정렬되어 있다. 

- 장점: 선형 검색보다 좀 더 빠르게 검색할 수 있음

- 한 단계를 진행할 때마다 검색 범위가 거의 반씩 좁혀짐

- 검색 종료 조건 (둘 중 하나라도 성립되면 종료됨)

① arr[pc](검사 요소, 중앙 요소)와 key가 일치하는 경우 (발견한 요소의 인덱스 반환)

② 검색 범위가 더 이상 없는 경우 (-1 반환)

static int binSearch(int[] arr, int n, int key) {
    int pl = 0;         // 검색 범위의 첫 인덱스
    int pr = n - 1;     // 검색 범위의 끝 인덱스

    do {
        int pc = (pl + pr) / 2;     // 중앙 요소의 인덱스
        if (arr[pc] == key)
            return pc;
        else if (arr[pc] < key)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while (pl <= pr);

    return -1;
}

- Java는 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공한다.

→ java.util.Arrays 클래스의 binarySearch() 메서드

: 모든 자료형 배열에서 검색 가능

: 검색 성공한 경우 → 찾은 요소의 인덱스 반환

: 검색 실패한 경우 → 음수 반환(-삽입포인트-1)

 *삽입포인트: 검색 key 보다 큰 요소 중 첫 번째 요소의 인덱스

 

+) String 클래스는 Comparable<T> 인터페이스와 compareTo() 메서드를 구현하고 있다.

내가 만든 클래스 A로 정렬 구현하려면,

// Comparable<T> 인터페이스 구현
class A implements Comparable<A> {

	// compareTo() 메서드 구현
	public int compareTo(A a) { 
    	// this가 a보다 크면 양수 반환
        // this가 a보다 작으면 음수 반환
        // this가 a와 같으면 0 반환
    }
    
    // equals() 메서드 구현
    public boolean equals(Object obj) {
    	// this가 obj와 같으면 true 반환
        // this가 obj와 다르면 false 반환
    }
}

- 자연 정렬로 정렬되지 않은 배열에서 검색하기: 제너릭 메서드(generic method) 사용

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

→ 3번째 매개변수에 comparator를 전달해야 한다.

+)  java.util.Comparator 인터페이스

+) comparator를 직접 구현하려면, Comparator 인터페이스를 구현한 클래스를 정의하고, 두 객체의 대소 관계를 비교하여 결과를 반환하는 compare() 메서드를 구현한다.

그리고 그 클래스형 인스턴스를 생성해야 한다.

import java.util.Comparator;

class X {
    // 클래스형 인스턴스 생성
    public static final Comparator<T> COMPARATOR = new Comp();

    // compare() 메서드 구현
    private static class Comp implements Comparator<T> {
        public int compare(T o1, T o2) {
            // o1이 o2보다 크면 양수 반환
            // o1이 o2보다 작으면 음수 반환
            // o1과 o2가 같으면 0 반환
        }
    }
}

→ binarySearch()의 세번째 매개변수로 X.COMPARATOR 로 전달해주면 된다.

→  꼭 찾으려는 값으로 정렬되어 있어야 함!!!!

 

+)

- 복잡도: 차원이 가장 높은 복잡도를 선택함

- 복잡도 대소 관계

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(n^k) < O(2ⁿ) < O(n!)