이진탐색 - 1. 똑같은 값 찾기

https://st-lab.tistory.com/261
해당 블로그는 이진탐색이 너무나 정리가 잘되어있다.
(위 블로그에서 참고하여 작성한 문서입니다.)

---

1. 첫번째 유형 똑같은 값 찾기 이다.

 

1. 문제

https://www.acmicpc.net/problem/1920

2. 풀이

즉 해당 값이 있냐 없냐의 문제이다.

2-1. ✨핵심 Point

1. 이진탐색에서 Sort는 필수이다.

Arrays.sort(arr);

2. 1) start와 end값이 같은 값에 대해서도 확인해야하기 때문에 while(start <= end) 이다!
   2) 찾는 값이 있을경우와 아닌경우 3가지로 나누어서 처리해준다.(문제가 값을 찾는 것이기 때문!)

1. 찾는 값이 있을 경우(check == arr[mid]
2. 찾는 값이 없을 경우

• arr[mid]는 이미 비교작업을 했으니 mid를 제외한 범위를 탐색 범위로 보면 되는 것이다.
  • start = mid + 1
  • end = mid - 1

while(start <= end){
	int mid = (start + end) / 2;
	if(check == arr[mid]){
		return(1);
	} else if(check > arr[mid]){
		start = mid + 1;
	} else {
		end = mid - 1;
	}
}
return(0);

3. 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String arsg[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine(), " ");
        for(int m = 0; m < M; m++){
            int check = Integer.parseInt(st.nextToken());
            sb.append(binaryF(arr, check)).append(' ');
        }
        System.out.println(sb.toString());
    }
    
    public static int binaryF(int arr[], int check) {
        int start = 0;
        int end = arr.length - 1;
        
        while(start <= end){
            int mid = (start + end) / 2;
            
            if(check == arr[mid]){
                return(1);
            } else if(check > arr[mid]){
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return(0);
    }
}