이분검색

 

설명

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

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

 

입력

첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.

두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.

 

출력

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

 

예시 입력 1 

8 32
23 87 65 12 57 32 99 81

 

예시 출력 1

3

 

 

문제 해결

 

이분 검색이란 

 

길이가 N인 정수 배열을 생성 후 우선 오름차순으로 정렬해준다. 이분 검색을 하기 위해서는 정렬을 먼저 해줘야 한다.

 

Arrays.sort(num);

 

 

이분 검색을 위해 왼쪽 인덱스는 0, 오른쪽 인덱스는 N-1로 초기화하고, 찾는 위치를 저장할 변수 position을 만들어 -1로 초기값을 설정해준다.

 

int left = 0;
int right = N - 1;
int position = -1; // 초기 위치 값

 

 

왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같은 동안 while 문을 돌아준다.

현재 검색 범위의 중간 위치를 계산하고,

• 이 때의 값이 찾는 값과 같다면 이를 position에 저장하고 반복문을 빠져나간다.
• 이 때의 값이 찾는 값보다 작으면 왼쪽 범위를 중간보다 한 칸 오른쪽으로 이동한다.
• 이 때의 값이 찾는 값보다 크면 오른쪽 범위를 중간보다 한 칸 왼쪽으로 이동한다.

 

while (left <= right) {
    int mid = (left + right) / 2; // 중간 위치
    if (num[mid] == M) {
        position = mid;
        break;
    } else if (num[mid] < M) {
        left = mid + 1; // 중간값보다 찾는 값이 크면 왼쪽 범위 줄임
    } else {
        right = mid - 1; // 중간값보다 찾는 값이 작으면 오른쪽 범위 줄임
    }
}

 

 

이런식으로 범위를 좁혀가며 위 과정을 반복해주며 위치를 찾아주면 된다.

 

 

최종 코드

 

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

public class P08_이분검색 {
    public static void main(String[] args) {
        //이분 검색 : 정렬된 배열에서 탐색 범위를 절반씩 줄여가며 찾아가는 방법
        //12 23 32 57 65 81 87 99
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[] num = new int[N];

        for(int i = 0; i < N; i++) {
            num[i] = in.nextInt();
        }
        Arrays.sort(num);

        int left = 0;
        int right = N - 1;
        int position = -1; // 초기 위치 값

        while (left <= right) {
            int mid = (left + right) / 2; // 중간 위치
            if (num[mid] == M) {
                position = mid;
                break;
            } else if (num[mid] < M) {
                left = mid + 1; // 중간값보다 찾는 값이 크면 왼쪽 범위 줄임
            } else {
                right = mid - 1; // 중간값보다 찾는 값이 작으면 오른쪽 범위 줄임
            }
        }
        System.out.println(position + 1);
    }
}