https://www.acmicpc.net/problem/1920 ## 이진 탐색이란
데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음
원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘
구현 및 원리가 비교적 간단하므로 많은 코딩테스트에서 부분 문제로 요구함
오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복
※ 내림차순이면 조건을 반대로 반복
가. 현재 데이터의 중앙값 선택
나. 중앙값 > 타깃 데이터 일때 중아갓 기준으로 원쪽 데이터셋을 선택
다. 중앙값 < 타깃 데이터 일때 중앙값 기준으로 오른쪽 데이터셋을 선택
라. 과정 가~다를 반복하다가 중앙값이 타깃 데이터 일 때 탐색을 종료
======================================================================================================
package backup;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
public class Main02 {
public static void main(String[]args)throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int []dataArr = new int[n];
for(int i=0;i<n;i++){
dataArr[i] = sc.nextInt();
}
Arrays.sort(dataArr);
int m = sc.nextInt();
for(int i=0;i<m;i++){
boolean find = false;
int target = sc.nextInt();
int left = 0;
int right = dataArr.length-1;
while (left<=right){
int mid = (left+right)/2;
int midValue = dataArr[mid];
if(midValue>target){
right = mid -1;
}else if(midValue<target){
left = mid +1;
}else{
find=true;
break;
}
}
if(find){
System.out.println(1);
}else{
System.out.println(0);
}
}
}
}
======================================================================================================