JUNGOL[3517] - 이진탐색(Binary Search-이진검색)

링크

JUNGOL[3517]

문제설명

• 이진탐색

문제풀이

• 이진탐색

문제코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main3517 {
    public static int[] ai;
    public static int BiS(int[] arr, int target) {
        int N = arr.length;
        int high=N-1;
        int low=0;
        int mid=(high+low)/2;

        while(low<=high) {    //못찾는 경우 
            if(arr[mid]>target) {
                high = mid-1;
            }
            else if(arr[mid]==target) {
                return mid;
            }
            else {    //arr[mid]<target
                low = mid+1;
            }
            mid=(high+low)/2;
        }
        return -1;
    }

    public static int BiS2(int find, int start, int end) {
//        못 찾은 경우
        if(start>end) return -1;
//        중앙 값
        int mid = (start+end)/2;
//        비교
        int data = ai[mid];

        if(find==data) {
            return mid;
        }
        else if(find<data) {
            return BiS2(find,start,mid-1);
        }
        else {    //find>data
            return BiS2(find,mid+1,end);
        }
    }


    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/jungol/3517.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int ans=0;

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        ai = new int[N];
        for (int i = 0; i < N; i++) {
            ai[i]=Integer.parseInt(st.nextToken());
        }

        int Q = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");
        for (int i = 0; i < Q; i++) {
//            bw.write((BiS(ai,Integer.parseInt(st.nextToken()))+" "));
            bw.write((BiS2(Integer.parseInt(st.nextToken()),0,N-1)+" "));
        }
        br.close();
        bw.close();
    }
}

아쉬운점

• 탈출구분 (low>high) 이해해야했음

잘한점

• Buffer read/output 사용