이분탐색

lt			mid				rt
10	12	14	16	20	22	25	30

 

mid = (lt+rt) / 2 = (0+7) / 2

a[mid] > m → rt = mid - 1

a[mid] < m → lt = mid + 1

 

public static int solution(int n, int m, int[] a) {
        int answer = 0;
        Arrays.sort(a);
        int lt = 0, rt = n - 1;
        while(lt <= rt) {
            int mid = (lt + rt) / 2;
            if(a[mid] == m) {
                answer = mid + 1;
                break;
            } else if(a[mid] > m){
                rt = mid - 1;
            } else {
                lt = mid + 1;
            }
        }
        return answer;
    }

 

 

 

출처 : 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비