binSearch

문제

이진 검색 과정을 자세히 출력하는 프로그램 작성하세요

각 행의 맨 왼쪽에 현재 선택한 요소의 인덱스를 출력하고, 검색 범위의 첫 요소위에 <-, 끝 요소 위에 ->, 현재 선택한 중양 요소위에 +를 출력하세요.

package Basic.Chap03;

import java.util.Scanner;

public class BinSearch2 {
    static int binSearch(int[] a, int n, int key) {
        System.out.print("   |");
        for (int k = 0; k < n; k++) {
            System.out.printf("%4d", k);
        }
        System.out.println();

        System.out.print("---+");
        for (int k = 0; k < 4 * n + 2; k++){
            System.out.print("-");
        }
        System.out.println();

        int pl = 0;            // 검색 범위 맨앞의 인덱스
        int pr = n - 1;        // 　 〃    　맨끝의 인덱스

        do {
            int   pc = (pl + pr) / 2;        // 중앙요소의 인덱스
            System.out.print("   |");
            if (pl != pc){
                System.out.printf(String.format("%%%ds<-%%%ds+",
                                (pl * 4) + 1, (pc - pl) * 4),
                        "", "");
            }
            else{
                System.out.printf(String.format("%%%ds<-+",   pc * 4 + 1), "");
            }
            if (pc != pr){
                System.out.printf(String.format("%%%ds->\n",
                        (pr - pc) * 4 - 2), "");
            }
            else{
                System.out.println("->");
            }
            System.out.printf("%3d|", pc);
            for (int k = 0; k < n; k++){
                System.out.printf("%4d", a[k]);
            }
            System.out.println("\n   |");
            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 stdIn = new Scanner(System.in);

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

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

        System.out.print("x[0] : ");        // 맨앞 요소를 입력받음
        x[0] = stdIn.nextInt();

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

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

        int idx = binSearch(x, num, ky);    // 배열 x에서 값이 ky인 요소를 검색

        if (idx == -1){
            System.out.println("그 값의 요소는 존재하지 않습니다.");
        }
        else{
            System.out.println("그 값은 x[" + idx + "]에 있습니다.");
        }
    }
}

 

binSearch 메서드

• 배열의 인덱스를 참조하기 위해 헤더로 배열의 인덱스를 출력합니다.
• 이진 탐색 알고리즘을 사용하여 배열 안에서 key 값을 찾습니다.
• 검색 범위를 pl (왼쪽)과 pr (오른쪽) 포인터로 유지합니다.
• 각 반복에서 중간 요소 pc를 계산하고 검색 범위를 그에 맞게 조정합니다.
• 메서드는 각 단계에서 현재 고려 중인 검색 범위를 보여주며 검색 과정의 진행 상황을 출력합니다.

작동 방식

• 사용자는 요소의 수 및 오름차순 배열 값에 대한 입력을 제공합니다.
• 사용자는 검색할 값을 (ky) 입력합니다.
• 이진 탐색 알고리즘(binSearch)이 실행되어 배열 안에서 ky 값을 찾습니다.
• 프로그램은 값이 발견된 인덱스를 출력하거나 값이 배열에 존재하지 않음을 알립니다. 검색 범위가 빈 상태가 되면(pl이 pr을 초과함) 값을 찾을 수 없다는 메시지를 출력합니다.

결과값