3-3. 이진 검색(Binary Search)

<이진 검색>

: 데이터가 키 값으로 이미 정렬(sort)되어 있을 때, 선형 검색보다 빠르게 검색 가능

요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

 

 

 

・이진 검색 알고리즘의 종료 조건

① a[pc]와 key가 일치하는 경우(검색 성공): 대략 ⌈log(n-1)⌉회 비교

② 검색 범위가 더 이상 없는 경우(검색 실패): ⌈log(n+1)⌉회 비교

 

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

 

 

 

 

 

<복잡도(Complexity)>

: 알고리즘의 성능을 객관적으로 평가하는 기준

 

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

 

 

 

 

 

・선형 검색의 시간 복잡도

 

	static int seqSearch(int[] a, int n, int key) {
1    	int i = 0;
2    	while(i < n) {
3        	if(a[i] == key)
4            	return i;
5        	i++;
    	}
6    	return -1;
	}

 

단계	실행 횟수	복잡도
1	1	O(1)
2	n/2	O(n)
3	n/2	O(n)
4	1	O(1)
5	n/2	O(n)
6	1	O(1)

 

 

 

-2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)

 

 

 

 

 

・이진 검색의 시간 복잡도

 

	static int binSearch(int[] a, int n, int key) {
1			int pl = 0;
2			int pr = n - 1;
		
			do {
3				int pc = (pl + pr) / 2;
4				if(a[pc] == key) 
5					return pc;
6				else if(a[pc] < key)
7					pl = pc + 1;
				else
8					pr = pc - 1;
9			} while(pl <= pr);
		
10			return -1;
		}

 

단계	실행 횟수	복잡도
1	1	O(1)
2	1	O(1)
3	log n	O(log n)
4	log n	O(log n)
5	1	O(1)
6	log n	O(log n)
7	log n	O(log n)
8	log n	O(log n)
9	log n	O(log n)
10	1	O(1)

 

 

 

-이진 검색 알고리즘의 복잡도

O(1) + O(1) + O(log n) + O(log n) + O(1) + ... + O(1) = O(log n)

 

 

 

 

 

<Arrays.binarySearch에 의한 이진 검색>

: Java에서 제공하는 배열에서의 이진 검색 표준 라이브러리의 메서드

 

-직접 코딩할 필요가 없어짐

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

 

 

 

・기본 자료형 배열에서 binarySearch 메서도 사용

 

int idx = Arrays.binarySearch(x, ky);
        
if(idx < 0)
    System.out.println("해당 값 없음");
        
else
    System.out.println(ky + "은(는) x[" + idx + "]");

 

 

 

 

 

・객체의 배열에서 검색

 

1. static int binarySearch(Object[] a, Object key)
자연 정렬이라는 방법으로 요소의 대소 관계를 판단. 정수 배열, 문자열 배열에서 검색할 때 적합.

2. static <T>int binarySearch(T[] a, T key, Comparator<? super T> c)
"자연 순서"가 아닌 순서로 줄지어 있는 배열에서 검색하거나
"자연 순서"를 논리적으로 갖지 않는 클래스 배열에서 검색할 때 적합.

 

 

 

2. 자연 정렬로 정렬되지 않은 배열에서 검색

: 제네릭 메서드 사용. 자료형에 구애받지는 않지만, 배열의 요소가 어떤 순서로 줄지어 있는지, 각 요소에 대소 관계를 어떻게 판단할 것인지에 대해서는 binarySearch 메서드에 알려주어야 한다.

 

public static final Comparator<T> COMPARATOR = new Comp();

private static class Comp implements Comparator<T> {
	public int compare(T d1, T d2) {
		//d1이 d2보다 크면 양의 값 반환
		//di이 d2보다 작으면 음의 값 반환
		//같으면 0 반환
	}

 

 

 

 

 

・제네릭

: 처리해야 할 대상의 자료형에 의존하지 않는 클래스(인터페이스) 구현 방식. 클래스 이름 바로 뒤에 <Type>같은 형식의 파라미터를 붙여 선언한다.

 

class 클래스 이름 <파라미터> { }
interface 인터페이스 이름 <파라미터> { }

 * 파라미터를 쉼표로 구분하면 여러 개의 파라미터를 지정할 수 있다.

 

 

 

-제네릭 클래스의 예

static class GenericClass<T> {
        private T xyz;
        
        GenericClass(T t) {
            this.xyz = t;
        }
        
        T getXyz() {
            return xyz;
        }
    }
    
    public static void main(String[] args) {
        GenericClass<String> s = new GenericClass<String>("ABC");
        GenericClass<Integer> i = new GenericClass<Integer>(15);
        
        System.out.println(s.getXyz());
        System.out.println(i.getXyz());
    }