Algorithm - Binary Search

• 2023-12-13 에 풀이한 문제
• 풀이 시간 : 09:10 ~ 09:27

• 나의 풀이 깃허브 : 풀이 클릭!

알고리즘 문제(Java) : 이진 탐색 ( 배열 )

1. 문제

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

2. 입력

• 첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
• 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

3. 출력

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

4. 문제 풀이

• 배열에서 이진 탐색을 하는 방법은, 먼저 Arrays.sort(arr); 를 활용하여 정렬을 해준다.
• 만약 내림차순이라면 Boxing을 통해 Wrapper 타입으로 만들어 준 후, Arrays.sort(arr, Collections.reverseOrder()); 를 해준다.
• 그 후, 범위를 지정한다.
  • 처음에는 배열 전체의 가운데를 선택할 것이기 때문에, lt = 0, rt = 배열길이 - 1 을 해준다.
• int mid = (lt + rt) / 2로 가운데 배열을 구한다.
• arr[mid] 가 내가 구하려는 값이라면 return 해주고, 그게 아니라면 내가 구하려고 하는 수와 비교한다.
  • arr[mid] > m 이라면 내가 구하려는 수보다 현재 수가 크니까 rt를 좁히고,
  • arr[mid] < m 이라면 내가 구하려는 수보다 현재 수가 작은거니까 lt를 좁힌다.
• 좁힌 범위에서 다시 가운데를 구하고, 동일하게 비교해준다.
• 아래 코드에서는 answer 를 0으로 시작했지만, 문제에 따라 없을 경우 -1을 return 하라는 조건이 붙기도하니 잘 확인해야 한다.

public class Binary_Search {

    public static int solution(int n, int m, int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        int lt = 0;
        int rt = n-1;

        while (lt <= rt) {
            int mid = ( lt + rt ) / 2;
            if ( arr[mid] == m ) {
                answer = mid + 1;
                break;
            }
            else if ( arr[mid] < m ) {
                lt = mid + 1;
            } else {
                rt = mid - 1;
            }
        }
        return answer;
    }

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

}