JAVA_[이진탐색]_ver1

코드 ver0.1

package freefree;

import java.util.Scanner;

public class Task {
	
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //사용자로부터 입력값 받기위해 Scanner클래스 선언
        System.out.println("숫자 범위를 입력하세요.");
        int maxNum = scanner.nextInt();
        // 사용자가 입력한 값 저장하기, maxNum은 30이라 가정
        int[] array = new int[maxNum];
        // 사용자가 입력한 값만큼 배열 저장공간 생성
        for (int i = 0; i < array.length; i++) {	// 배열의 길이만큼 반복
            array[i] = i + 1;	// array 배열 첫번째 저장공간(==array[0])에 1이 저장
        }
        //숫자 범위를 지정해서 array라는 int타입 배열에 담기

        System.out.println("1부터 " + maxNum + "까지의 숫자 중 하나를 생각하세요.");

        int result = -1;	//결과값에 -1(false)담기
        int left = 0;		
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2; //계산한 값은 14.5이지만 int끼리 계산이므로 소수점은 없다. (디버깅표참조)

            System.out.println("현재 추측한 숫자는 " + array[mid] + "입니다."); //array[14] == 15 (디버깅표참조)
            System.out.println("맞으면 0, 작으면 -1, 크면 1을 입력하세요: ");

            int select = scanner.nextInt();

            if (select == 0) {
                // 찾았을 때
                result = array[mid];
                break;
            } else if (select < 0) {
                // 작은 경우
                right = mid - 1;	//범위 좁히기 : 최대값을 현재의 중간값에 -1을 해줌
            } else {
                // 큰 경우
                left = mid + 1;		//범위 좁히기 : 최소값을 현재의 중간값에 +1을 해줌
            }
        }

        if(result != -1){
            System.out.println("찾는 숫자는 " + result + "입니다!^^");
        }
        else{
            System.out.println("숫자를 찾지 못했습니다ㅠㅠ");	//범위 밖의 숫자를 입력했을때
        }
    }
}

 

예시 디버깅표

사용자가 원하는 범위 : 1~30

사용자가 생각하는 숫자 : 20

left <= right	left (0)	right (29)	mid (left+right/2)	변환값
T (0<=29)	0	29	14 ((0+29)/2)	left = mid + 1 = 15
T (15<=29)	15	29	22 ((15+29)/2)	right = mid - 1 = 21
T (15<=21)	15	21	18 ((15+21)/2)	left = mid + 1 = 19
T (19<=21)	19	21	20 ((19+21)/2)	right = mid - 1 = 19
T (19<=19)	19	19	19 ((19+19)/2)	result = array[19] = 20 break;