[인프런 알고리즘] Chapter 6, 8번 문제(이분검색)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class sec06_08 {
    public static int solution(int[] arr, int M) {
        Arrays.sort(arr);
        return Arrays.binarySearch(arr, M) + 1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr, M));
    }
}

 

이진탐색 구현

public static int solution(int[] arr, int M) {
    Arrays.sort(arr);
    int lPtr = 0; int rPtr = arr.length - 1;
    while(lPtr <= rPtr)
    {
        int mid = (lPtr + rPtr) / 2;
        if(arr[mid] == M) return mid + 1;
        else
        {
            if(arr[mid] > M) rPtr = mid - 1;
            else lPtr = mid + 1;
        }
    }
    return -1;
}

 

설명

• 이진 탐색을 수행하기 위해서는 배열이 반드시 정렬되어 있어야 한다.
• 이진 탐색은 정렬된 배열에서 중앙값을 기준으로 탐색 범위를 줄여나가는 방식이기 때문에, 정렬되지 않은 배열에서는 제대로 작동하지 않는다.
• Arrays.binarySearch(arr, M)는 arr 배열에서 값 M을 찾는 이진 탐색 메서드이다. 반환 값은 M의 인덱스이다.
  만약 M을 찾지 못한다면 음수를 반환한다.