[JAVA/코딩테스트] 이분검색

* 이분검색이란? 리스트에서 반을 쪼개 맞는지 확인후 다시 쪼개서 확인하고 그 작업을 반복하여 검색

 

설명

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

입력

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

출력

첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.

예시 입력 1 

8 32 23 87 65 12 57 32 99 81

예시 출력 1

3

 

 

import java.util.*;

class Main {
	
	public void solution(int n, int m, List<Integer> list) {
		
		int result = 0;
		int lt = 0; 
		int rt = list.size();
		int mid= rt/2;
		
		Collections.sort(list);
		
		while(list.get(mid).intValue() != m) {
			if(list.get(mid).intValue() > m) {
				rt = mid;
				mid = (lt+rt)/2;
			}else {
				lt = mid;
				mid = (lt+rt)/2;
			}
		}
		
		result = mid+1;
		
		System.out.println(result);
		
		
	};
	
	public static void main(String args[]) {
		
		Main main = new Main();
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int M = in.nextInt();
		
		List<Integer> list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			list.add(in.nextInt()); 
		}
		
		main.solution(N, M, list);
		 
    }

}