배열검색 (이진검색)

 

이진검색

 

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

배열의 가운데 인덱스와 찾고싶은 값을 비교하면서 검색범위를 반씩 줄여가며 원하는 값을 찾아낸다.

[ O(log n) ]

import java.util.*;

public class Main {
    //길이가 n인 배열 a에서 key를 이진검색합니다.
    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) //key가 중간값보다 컸으므로 앞에 절반은 날림
                pl = pc+1;
            else //key가 중간값보다 작았으므로 뒤에 절반은 날림
                pr = pc-1;
        }while (pl<=pr);
        return -1; //검색 실패
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("배열의 길이:");
        int num = scanner.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력:");
        System.out.print("x[0]:");
        x[0] = scanner.nextInt();

        for (int i = 1; i < num; i++) {
            do{
                System.out.print("x["+i+"]:");
                x[i] = scanner.nextInt();
            }while(x[i]<x[i-1]);
        }

        System.out.print("검색할 값:");
        int ky = scanner.nextInt();
        int idx = binSearch(x, num, ky);

        if(idx==-1)
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(ky+"는 x["+idx+"]에 있습니다.");
    }
}

 

자바 binarySearch

그리고 자바는 이렇게 배열에서 이진검색을 하는 메서드를 표준 라이브러리로 제공한다.

바로 java.util.Arrays 클래스의 binarySearch메서드이다.

자료형에 따라 여러방법으로 오버로딩되어있다.

이는 이진검색 메서드를 직접 코딩할 필요가 없고, 모든 자료형 배열에서 검색할 수 있다는 장점이 있다.

1. 검색에 성공

key와 일치하는 요소가 배열에 여러개인 경우,

맨 앞의 인덱스나 특정 인덱스가 아닌 무작위의 인덱스를 반환한다는 점을 주의해야한다.

 

2. 검색에 실패

삽입포인트(key보다 큰 첫번째 값의 인덱스)가 x라면 -x-1을 반환한다.

 

예를 들어, 배열이 {1, 2, 3, 5, 6, 8, 9}이고 key = 4라면

4보다 큰 첫번째값은 5이고 그 인덱스는 3이므로,

삽입포인트는 3, 반환값은 -4가 된다.

 

그런데 만약 배열의 모든 요소가 key보다 작다면 배열의 길이를 삽입포인트로 정한다.

 

예를 들어, 배열이 {5, 7, 15, 28, 29, 31, 39, 58, 68, 70}이고 key=30이라면

배열의 모든 요소가 30보다 작으므로,

삽입포인트는 배열의 길이인 10, 반환값은 -11이 된다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("배열의 길이:");
        int num = scanner.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력:");
        System.out.print("x[0]:");
        x[0] = scanner.nextInt();

        for (int i = 1; i < num; i++) {
            do{
                System.out.print("x["+i+"]:");
                x[i] = scanner.nextInt();
            }while(x[i]<x[i-1]);
        }

        System.out.print("검색할 값:");
        int ky = scanner.nextInt();
        int idx = Arrays.binarySearch(x, ky); //배열 x에서 키값이 ky인 요소를 검색

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

 

객체의 배열에서 검색하기

또한 검색은 객체의 배열에서도 가능하다.

 

A. 자연정렬로 정렬된 배열에서 검색하기

static int binarySearch(Object[] a, Object key)

자연정렬로 요소의 대소관계를 판단하기 때문에 정수배열, 문자열배열에서 검색할때 적당하다.

다음은 위 메서드를 사용하여 String객체의 배열에서 검색하는 코드이다.

//자연 정렬로 정렬된 배열에서 검색하기
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String[] x = {
                "abstract",   "assert",       "boolean",   "break",      "byte",
                "case",       "catch",        "char",      "class",      "const",
                "continue",   "default",      "do",        "double",     "else",
                "enum",       "extends",      "final",     "finally",    "float",
                "for",        "goto",         "if",        "implements", "import",
                "instanceof", "int",          "interface", "long",       "native",
                "new",        "package",      "private",   "protected",  "public",
                "return",     "short",        "static",    "strictfp",   "super",
                "switch",     "synchronized", "this",      "throw",      "throws",
                "transient",  "try",          "void",      "volatile",   "while"
        };

        System.out.print("원하는 키워드를 입력하세요: ");
        String ky = scanner.next();
        int idx = Arrays.binarySearch(x, ky);

        if(idx<0)
            System.out.println("해당 키워드가 없습니다!");
        else
            System.out.println("해당 키워드는 x["+idx+"]에 있습니다!");
    }
}

 

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

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

자연정렬로 정렬되지 않은 배열에서의 검색은 제너릭메서드로 하면 된당.

import java.util.*;

public class Main {
    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;
        }

        public String toString(){ //객체출력시 호출되는 toSting 오버라이딩해줌
            return name+" "+height+" "+vision;
        }

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

        private static class HeightOrderComparator implements Comparator<PhyscData>{
            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) {
        Scanner scanner = new Scanner(System.in);
        
        // 키의 오름차순으로 정렬되어 있습니다.
        PhyscData[] x = {              
                new PhyscData("권지아", 157, 0.8),
                new PhyscData("이나령", 162, 0.3),
                new PhyscData("유지훈", 168, 0.4),
                new PhyscData("홍준기", 171, 1.5),
                new PhyscData("이호연", 174, 1.2),
                new PhyscData("김민수", 178, 1.5),
                new PhyscData("이윤환", 186, 0.7),
        };

        System.out.println("몇 cm인 사람을 찾고있나요?");
        int height = scanner.nextInt(); //키 값 입력
        int idx = Arrays.binarySearch(
                x, //배열 x에서
                new PhyscData("", height, 0.0), //키가 height인 요소를
                PhyscData.HEIGHT_ORDER //HEIGHT_ORDER라는 comparator에 의해 검색
        );

        if (idx < 0)
            System.out.println("요소가 없습니다.");
        else {
            System.out.println("x[" + idx + "]에 있습니다.");
            System.out.println("찾은 데이터：" + x[idx]); //객체를 출력하면 자동으로 toString메서드가 호출됨.
        }
    }
}