이진탐색: Hunt The Rabbit (백준 13777)

○ 문제
Farkle 씨는 농장에서 자랐고 어린 시절 토끼 사냥에 상당한 시간을 보냈습니다! 
그는 현재 수학과 컴퓨팅을 가르치고 있으며 학생들이 이진 검색에 대해 배울 수 있도록 사냥 게임을 고안했습니다.
그는 방 앞에 1부터 50까지 번호가 매겨진 50개의 봉투를 놓았습니다. 그 봉투 안에는 토끼를 숨겼습니다. 물론 진짜는 아니지만 토끼 그림이 있는 카드였습니다! 
그런 다음 그는 다른 모든 봉투에 카드를 넣어 토끼가 들고 있는 것보다 낮은 숫자가 있는 봉투를 선택하면 카드에 "더 높은 숫자를 시도하십시오"라고 표시하고, 그렇지 않으면 카드에 "낮은 숫자를 시도하십시오"라고 표시합니다.
학생들은 이진 검색을 사용하여 토끼를 찾아야 하고 검색하는 동안 개봉한 모든 봉투의 번호를 (순서대로) 적어야 합니다. 이진 검색에서는 검색하는 범위에서 중간 엔벨로프를 선택해야 합니다. 
이것은 봉투가 홀수일 경우 찾기 쉽지만, 짝수일 경우 가운데 봉투 2개 중 낮은 번호를 선택해야 합니다. 
이는 25가 항상 첫 번째로 확인되는 봉투임을 의미합니다.

○ 입력
입력의 각 줄은 1에서 50까지 범위의 단일 숫자이며 Farkle 씨가 토끼를 숨긴 봉투의 숫자입니다. 최종 입력은 처리되지 않아야 하는 0이 됩니다.

○ 출력
입력의 각 행에 대해 토끼를 찾을 때까지 열린 순서대로 모든 봉투가 열린 수를 출력하십시오. 각 번호는 이전 번호와 공백으로 구분된 동일한 줄에 있어야 합니다.

○ 예제 입력
25
17
31
0

○ 예제 출력
25
25 12 18 15 16 17
25 38 31

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
	static int[] card = new int[50];	//카드 배열
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		//배열 원소 초기화
		for (int i = 0; i < card.length; i++) {
			card[i] = i+1;
		}
		
		//토끼 입력: EOF=>"0" 및 탐색
		String str = new String();
		while (!(str = br.readLine()).equals("0")) {
			int num = Integer.parseInt(str);
			sb.append(binarySearch(num)).append("\n");
		}
		
		bw.write(sb.toString());
	
		bw.flush();
		bw.close();
		
	}
	
	public static String binarySearch(int target) {
		StringBuilder sb = new StringBuilder();
		int left = 0;
		int right = card.length -1;	//index
		
		while (left <= right) {
			int mid = (left + right) / 2;
			
			if (card[mid] == target) {
				sb.append(card[mid]);
				break;
				
			} else if (card[mid] < target) {
				left = mid + 1;
				
			} else {
				right = mid - 1;
				
			}
			
			sb.append(card[mid]).append(" ");

		}
		
		return sb.toString();
		
	}
	
}

○ 확인
- 배열 최대 값: Stream API - Arrays.stream() 메소드로 스트림 생성 후 스트림의 max().getAsInt() 메소드 사용
- 이진 탐색: 조회범위에서 중위 값을 찾아 범위를 반으로 나눈 후 아래로 탐색 진행, 없으면 위로 탐색 진행
- StringBuilder는 동기화를 지원하지 않아 single thread에서만 사용 가능 (싱글쓰레드, 동기화 고려하지 않을 시 퍼포먼스 더 좋음)
- StringBuffer는 동기화를 지원하기 때문에 multi-thread에서도 사용 가능