자바 Test> 이진 검색을 통해 찾는 과정 출력

갈고리 2015. 12. 24. 17:19

< 문제 >

/*

 * 1 ~ 100 까지의 정수를 입력받고 이분 검색을 통해 찾는 과정을 출력하라.

 *

 int[100] 배열에 1~100 정수를 입력하고 사용할 것.

 *

 *

 *

 입력 예)

 *      1~100 정수 입력 : 47

 *     

 출력 예)

 *      번째 검색 > 47  50보다 작은 1 ~ 49 사이의 수 이다.

 *      번째 검색 > 47  25보다 큰 26 ~ 49 사이의 수 이다.

 *      번째 검색 > 47  37보다 큰 38 ~ 49 사이의 수 이다.

 *      번째 검색 > 47  43보다 큰 44 ~ 49 사이의 수 이다.

 *      번째 검색 > 47  46보다 큰 47 ~ 49 사이의 수 이다.

 *      번째 검색 > 47  48보다 작은 47 ~ 47 사이의 수 이다.

 *      번째 검색 > 47  47과 같은 수 이다.

 *     

 *      결과 > 47 을 찾는데 총 7 번 검색하였습니다.

 */

 

 

 < 결과 >

 

 

 

 

 

 

 

 

 

 

 

 < 풀이소스 >

 

접기

package study.exam;

 

import java.util.*;

 

public class Ex16 {

 

    int count;              // 검색횟수

    int inputNum;           // 입력된 숫자

    int start;              // 검색 범위 시작 숫자

    int center;             // 비교할 검색 범위 중간 숫자

    int end;                // 검색 범위 끝 숫자

   

    int[] arr;              // 100까지 입력할 배열

   

   

    public static void main(String[] args) {

        new Ex16().execute();

    }

   

    // 실행

    public void execute() {

       

        setArray();             // 배열을 생성하고 100까지 입력한다.

        getInputNum();          // 숫자를 입력받는다.

        startSearch();          // 검색을 실행하며 과정을 출력한다.

    }

   

 

    // 배열을 생성하고 100까지 입력한다.

    public void setArray() {

       

        arr = new int[100];     // 1~100 저장할 배열 생성

       

        for(int i=0; i<arr.length; i++) {       // 배열에 100까지 입력

            arr[i] = i + 1;

        }

    }

   

    // 숫자를 입력받는다.

    public void getInputNum() {

        Scanner scan = new Scanner(System.in);

       

        while(true) {

            System.out.print("정수 입력 : ");

            try {

                inputNum = Integer.parseInt(scan.next());

                if(inputNum>100)

                    throw new Exception();

                else

                    break;

            catch (Exception e) {

                System.out.println("100이하의 정수만 입력하시오.");

            }

        }

       

    }//end getInputNum()

   

    // 검색을 실행한다.

    public void startSearch() {

       /*

        *  범위를 설정한다 (시작 : 1,  : 100)

        * 

        *  1 ~ 100 의 중간값 구한다.  -> (1 + 100) / 2 = 50

        * 

        *  입력받은 값 47을 중간값 50 과 비교한다.

        * 

        *  입력받은 값이 중간값 보다 작으면 범위를 재설정한다. (범위끝값에 중간값-1을 대입)

        * 

        *  입력받은 값이 중간값과 같으면 찾는 수이다.

        * 

        *  입력받은 값이 중간값 보다 크면 범위를 재설정한다. (범위시작값에 중간값+1을 대입)

        * 

        */

   

        start = arr[0];

        end = arr[arr.length-1];

       

        String bigSmall = "";

       

        while(inputNum!= center) {             // 입력값과 중간값이 같지 않을때 반복

           

            count++;

           

            center = (start + end) / 2;

           

            if(inputNum > center) {             // 입력값이 중간값보다 크면

               

                start = center + 1;

                bigSmall = "";

               

            }else if(inputNum < center) {       // 입력값이 중간값보다 작으면

               

                end = center - 1;

                bigSmall = "작은";

               

            else {

                break;

            }

           

           

            System.out.printf(

                    "%d 번째 검색 > %d  %d보다 %s %d ~ %d 사이의 수 이다.\n"count,

                    inputNumcenter, bigSmall, startend);

           

 

        }//end while

       

        System.out.printf("%d 번째 검색 > %d  %d과 같은 수 이다.\n",count,inputNum,center);

        System.out.println();

        System.out.printf("%d 을 찾는데 총 %d 번 검색하였습니다.\n",inputNum,count);

    }

 

   

}

'갈고리' 카테고리의 다른 글

test #4  (0) 2015.12.17