이분검색

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면

이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

 

!이분검색은 정렬된 상태에서만 사용 가능하다

 

이분검색을 기존에 알던 대로 lt 와 rt가 교차하기 전까지 도는 반복문에서

찾는 값이 mid 지점보다 크면 lt를 mid+1로 옮기고 작으면 rt를 mid-1로 옮겨서 풀었다.

 

import java.util.*;

class Main {
    public int solution(int n, int m, int[] arr){
        int ans = 0;
        int mid = n/2;
        int lt = 0;
        int rt = n-1;
        while (lt <= rt){
            mid = (lt+rt)/2;
            if(arr[mid] == m){
                return mid+1;
            }
            else if(arr[mid] > m) {
                rt = mid-1;
            }
            else lt = mid+1;
        }
        return ans;
    }

    public static void main(String[] args) {
            Main t = new Main();
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[] arr = new int[n];
            for(int i =0; i < n; i++) arr[i] = in.nextInt();
            Arrays.sort(arr);
            System.out.println(t.solution(n, m, arr));
    }
}

 

강의 풀이