이진검색[binary search]

이진 검색(binary search)

이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.

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

검색을 반복할 때마다 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다.

실패할 경우는 log(n+1)회, 검색에 성공한 경우는 log(n-1)회이다

• n개의 요소가 오름차순으로 늘어선 배열 a에서 키를 검색하는 과정을 일반적인 방법으로 표현하면
• 검색 범위 맨 앞 인덱스를 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);//배열 x에서 키 값이 ky인 요소를 검색

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

실행결과