검색 알고리즘 - 이진 검색

이진 검색

이진 검색(binary search)는 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 특정한 값을 검색하는 알고리즘

선형 검색보다 더 빠르개 검색할 수 있는 장점이 있다.

 

■ 이진 검색 알고리즘

이진 검색을 한 단계씩 진행할 때마다 검색 범위가 반으로 좁혀진다. 

검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 가정

검색을 시작할 때, pl은 0, pr은 (n-1), pc는 (n-1)/2으로 초기화 된다.

1) a[pc] < key 인 경우
a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외
검색 범위는 a[pc]보다 뒤쪽의 a[pc+1]~ a[pr]로 좁혀진다. 
그런 다음 pl의 값을 pc+1로 업데이트한다.

2) a[pc] > key 인 경우
a[pc]~a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외
검색 범위는 a[pc]보다 앞쪽의 a[pl]~a[pc-1]로 좁혀진다.
그런 다음 pr의 값을 pc-1로 업데이트한다.

[이진 검색 알고리즘의 종료 조건]
1) a[pc] == key 경우 
2) 검색 범위가 더 이상 없는 경우

public class BinSearch {

    public 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 {
                //a[pc] > key 경우
                pr = pc-1;
            }
        }while (pl <= pr);

        return -1;  //검색 실패

    }

    public static void main(String[] args) {
        int[] a = new int[]{15,27,39,77,92,108,121};
        int ky = 108;

        int idx = binSearch(a, a.length, ky);   //배열 a에서 키 값이 ky인 요소의 위치를 검색
        if(idx == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(ky + "은/는 [" + idx + "]에 있습니다." );
        }
    }
}

■ Arrays.binarySearch에 의한 이진 검색

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

이진 검색 표준 라이브러리의 메서드로는 java.util.Arrays 클래스의 binarySearch 메서드가 있다.

binarySearch 메서드는 오름차순으로 정렬된 배열 a를 가정, 키 값이 key인 요소를 이진 검색

binarySearch 메서드는 자료형에 따라 9가지 방법으로 오버로딩

[장점]
1) 이진 검색 메서드를 직접 코딩할 필요 없음
2) 모든 자료형 배열에서 검색 가능

import java.util.Arrays;

public class BinarySearchTaster {
    public static void main(String[] args) {
        int[] a = new int[]{15,27,39,77,92,108,121};
        int key = 77;
        int idx = Arrays.binarySearch(a, key);

        if(idx < 0){
            System.out.println("그 값의 요소가 없습니다.");
        }else {
            System.out.println(key + "은/는 [" + idx + "]에 있습니다." );
        }
    }
}

■ 연습문제

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

comparator를 활용

import java.util.Arrays;
import java.util.Comparator;

//신체검사 데이터 배열에서 이진 검색하기
public class PhysExamSearch {

    static class PhyscData {
        private String name;
        private int height;
        private double vision;

        public PhyscData(String name, int height, double vision) {
            this.name = name;
            this.height = height;
            this.vision = vision;
        }

        @Override
        public String toString() {
            return "PhyscData{" +
                    "name='" + name + '\'' +
                    ", height=" + height +
                    ", vision=" + vision +
                    '}';
        }

        //오름차순으로 정렬하기 위한 comparator
        public static final Comparator<PhyscData> Height_ORDER = new HeightOrderComparator();

        public static class HeightOrderComparator implements Comparator<PhyscData> {
        @Override
            public int compare(PhyscData d1, PhyscData d2) {
               return (d1.height > d2.height)? 1 : (d1.height < d2.height) ? -1 : 0;
            }
        }
    }
    public static void main(String[] args) {
        PhyscData[] x = {   //키의 오름차순으로 정렬되어 있어야 합니다.
                new PhyscData("유지훈", 165, 0.3),
                new PhyscData("김한결", 166, 0.4),
                new PhyscData("박한수", 167, 0.5),
                new PhyscData("배지수", 168, 0.6),
                new PhyscData("원수형", 169, 0.7),
                new PhyscData("김철수", 173, 0.1),
                new PhyscData("이나령", 174, 0.2)
        };

        int height = 173;
        int idx = Arrays.binarySearch(x, new PhyscData("", height, 0.0), PhyscData.Height_ORDER);

        if(idx < 0){
            System.out.println("요소가 없습니다.");
        }else {
            System.out.println("찾은 데이터 : " + x[idx]);
        }

    }
}