JAVA_이진검색

python 이진검색

https://velog.io/@whtjsdud54/python%EC%9D%B4%EC%A7%84%EA%B2%80%EC%83%89

java 이진검색

//정렬0
//중앙값 기준으로 비교 시작함
//pr, pl, pc

import java.util.*;
public class bin_search {

	public int bin_search(List <Integer> x,int key) { //This method must return a result of type int (error)
		int pl =0;
		int pr = (x.size()) - 1; //list는 x.size()함수 사용
		
		while(true) {
        	/*중앙값*/
			int pc = (pl + pr) /2;
            /*중앙값이 key와 같으면 pc리턴*/
			if (x.get(pc) == key)
				return pc;
            /*중앙값이 key보다 작으면 pl이 중앙값 위쪽으로 이동*/
            /*pc 이하는 값이 없으므로 신경쓰지 않는다.*/
			else if (x.get(pc) < key)
				pl = pc +1;
            /*중앙값이 key보다 크면 pr이 중앙값 아래쪽으로 이동*/
			else
				pr = pc -1;
            /*pl이 pr보다 클 수 없음*/
			if (pl > pr)
				break;
		return -1;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println();
		int num = sc.nextInt();
		sc.nextLine(); //버퍼 비우기
		
		//제네릭으로
		List<Integer> x = new ArrayList<Integer>(); //뒤에 Integer은 생략 가능
		
		System.out.println("x[0]: ");
		x.add(0, sc.nextInt()); //첫번째 위치에 nextInt()삽입
		sc.nextLine();
        
		for(int i=0; i<num; i++) {
			while(true) {
				System.out.println("x["+i+"]: ");
				x.add(i, sc.nextInt());
				sc.nextLine();
                
				if (x.get(i) >= x.get(i-1))
					//Arraylist는 get으로 접근 (값를 반환한다)
					//get은 string을 반환해주는 함수
					//int로 형변환 해줘야함
					//(int)로 하거나 parseInt 사용
					//list에 integer있으므로 get써도 int로 반환
					break;
             }
          }
                    
		System.out.println();
		int key = sc.nextInt();
		sc.nextLine();
		
		int idx = bin_search(x, key); //error
		if (idx == -1)
			System.out.print("못 찾음");
		else
			System.out.print(x.get(idx));
			}
	}

}

buffer 사용해서 이진검색 만들기

입출력 Buffer는 예외처리 해줘야함

• buffer는 checked Exception: 컴파일 시 발생되는 예외
• scanner는 UnChecked Exception: 컴파일 통과 후 런타임 시 발생할 수 있는 예외

멀티 스레드 환경의 경우 buffer가 안전

BufferedWriter == System.out.println()과 동일한 기능
writer의 경우 마지막에 bw.close(), bw.flush()를 사용해야함.
직접 stream에 반영되는 것이 아니라 buffer에 저장해뒀다가 flush되거나 close되었을 때 한 번에 stream에 반영

줄바꿈시 newLine()
string으로만 출력이 가능해 String.valueOf()를 통해 타입 변환

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

public class bin_search_buffer {

	public static int bin_search(List <Integer> x,int key) { //error
		int pl =0;
		int pr = (x.size()) - 1;
		
		while(true) {
			int pc = (pl + pr) /2;
			if (x.get(pc) == key)
				return pc;
			else if (x.get(pc) < key)
				pl = pc +1;
			else
				pr = pc -1;
			if (pl > pr)
				break;
		return -1;
		}
	}
    
    public static void main(String[] args) throws IOException { //throws문 혹은 try-catch문 필요
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine(); //비우기
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		System.out.println();
		int num = Integer.parseInt(br.readLine()); 
		//bufferedReader는 모두 string으로 인식하기 때문에 형변환 필요 
		
		//제네릭으로
		List<Integer> x = new ArrayList<Integer>(); //뒤에 Integer은 생략 가능
		
		bw.write("x[0]: ");
		String s = br.readLine(); //라인단위로 입력받기
		int ss = Integer.parseInt(br.readLine()); //형변환
		x.add(0, ss); //첫번째 위치에 nextInt()삽입
		
		for(int i=0; i<num; i++) {
			while(true) {
				bw.write("x["+String.valueOf(i)+"]: ");
				x.add(i, Integer.parseInt(br.readLine()));
				
				if (x.get(i) >= x.get(i-1))
					break;
			}
		}
		bw.write("");
		bw.flush();
		int key = Integer.parseInt(str);
		
		int idx = bin_search(x, key);
		if (idx == -1)
			bw.write("못찾음");
		else
			bw.write(String.valueOf(x.get(idx))); 
			//int형을 String으로 바꿔 출력해야함
		bw.flush(); //직접 stream에 반영되는 것이 아니라 buffer에 저장해뒀다가 flush되거나 close되었을 때 한 번에 stream에 반영
	bw.close();
	}

}

생각해보기

public int bin_search(List <Integer> x,int key)

-1을 반환하기 때문에 int로 선언했는데 이클립스는 void로 바꾸거나 int를 지우길 권함.

-> 왜?

int idx = bin_search(x, key);
//Cannot make a static reference to the non-static method bin_search(List<Integer>, int) from the type bin_search

idx에 값을 넣는 문장에서 static을 쓰지않아 에러가 남.

-> 굳이 써야하나?