[Algorithm]알고리즘 자바_50 이분검색

 

💬 문제 설명

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

 

 

🔨 입출력 예

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

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

8 32
23 87 65 12 57 32 99 81

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

3

 

 

​

💻 Solution.java

import java.util.*;

public class Main {
	
	public int solution(int n, int key, int[] arr) {
		int answer = 0;
		
		Arrays.sort(arr);
		
		for(int i = 0; i < n; i++) {
			if(arr[i] == key) {
				answer = i + 1;
				break;
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int key = sc.nextInt();
		
		int [] arr = new int [n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		System.out.println(main.solution(n, key, arr));
		
		sc.close();
		return ;
	}
}

 

 

이분 검색 Version

import java.util.*;

public class Main {
	
	public int solution(int n, int key, int[] arr) {
		int answer = 0;
		Arrays.sort(arr);
		int lt = 0, rt = n - 1;
        
        while(lt <= rt){
        	int mid = (lt + rt) / 2;
            if (arr[mid] == key){
            	answer = mid + 1;
                break;
            }
            if(arr[mid] > key) rt = mid - 1;
            else lt = mid + 1;
        }
		
		return answer;
	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int key = sc.nextInt();
		
		int [] arr = new int [n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		System.out.println(main.solution(n, key, arr));
		
		sc.close();
		return ;
	}
}