[Algorithm] 이진 검색

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

 

이진 검색으로 검색하는 과정을 일반적인 방법으로 표현하겠습니다.

 

검색 범위 맨 앞 인덱스 pl, 맨 끝은 pr, 중앙 인덱스를 pc로 지정,

검색을 시작할 때 pl =0, pr = n - 1, pc = (n - 1)/2로 초기화합니다.

 

이진을 검색을 한번 할 때마다 값을 못찾으면 범위가 반으로 줄어 듭니다.

검색할 요소가 해당 단계에서 다음에 검색할 범위의 준간 지점으로 단숨에 이동합니다.

 

public class BinSearch {

    //요소수가 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)
                pl = pc + 1; //검색 범위를 뒤쪽 절반으로 줄임
            else
                pr = pc - 1; //검색 범위를 앞쪽 절반으로 줄임
        }while (pl <= pr);
        return -1;  //검색 실패
    }

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

        System.out.print("요소수 : ");
        int num = sc.nextInt();
        int[] x = new int[num]; //요소수가 num 인 배열

        System.out.println("오름차순으로 입력하세요.");

        System.out.print("x[0] : "); //첫 요소 입력
        x[0] = sc.nextInt();

        for(int i=1; i<num; i++){
            do{
                System.out.print("x["+i+"] : ");
                x[i] = sc.nextInt();
            }while (x[i] < x[i-1]);   //바로 앞의 요소보다 작으면 다시 입력
        }

        System.out.print("검색할 값 : ");  //키값을 입력
        int ky = sc.nextInt();

        int idx = binSearch(x, num, ky);

        if(idx == -1) System.out.println("fail");
        else System.out.println(ky+"는 x["+idx+"]에 있습니다.");

    }
}

 

실행결과

요소수 : 3
오름차순으로 입력하세요.
x[0] : 1
x[1] : 2
x[2] : 3
검색할 값 : 4
fail