[JAVA] 알고리즘 : 정렬- 이분 검색

import java.util.Arrays;
import java.util.Scanner;

public class Main{

    public int solution(int n, int m, 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]==m){
                answer=mid+1;
                break;
            }
            if(arr[mid] >m) rt=mid-1;
            else lt=mid+1;
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] arr = new int[n];
        for(int i=0; i<n; i++) arr[i]=sc.nextInt();
        System.out.println(T.solution(n, m, arr));
    }
}

 

 

 

이분 검색을 하기 위해선 일단 배열을 오름차순 정렬한다.

 

lt			mid				rt
12	23	32	57	65	81	87	99

 

 

 

lt 는 첫번째 인덱스, rt는 마지막 인덱스, mid는 중간 번호 인덱스이다.

 

찾고자하는 숫자 32가 mid에 있는 숫자 57보다 작다. 그러면 mid이후의 원소들은 볼 필요가 없다.

그럼 rt를 mid-1로 옮긴다.  

 

 

 

 

lt	mid	rt
12	23	32

 

 

 

이제 mid에 있는 숫자 23이 찾고자하는 숫자 32보다 작다. 그럼 lt를 mid+1로 옮긴다. 

 

그럼 rt랑 lt가 같은 값을 가리켜 mid가 되고 while문을 빠져나온다. 

mid번째 원소가 찾고자하는 숫자 m과 같아, mid+1이 정답이된다.