[Algorithm] 이진탐색(Binary Search)

이진탐색이란?

"정렬되어 있는 데이터"에서 특정한 값을 찾아내는 알고리즘이다.

 

문제

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

입력

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

출력

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

 

이진탐색의 과정

1. 일단 배열을 정렬한다. (오름차순으로)

2. 답이 될 수 있는 최소값과 최대값의 범위를 구한다. (위의 문제에서는 최소값이 가장 작은 인덱스가 되고, 최대값이 가장 큰 인덱스가 될 것이다.)

3. 그리고 (최소값 + 최대값) / 2 의 중간값을 만든다. 만약 이 중간 인덱스의 값이 M보다 크다면 최대값을 이 중간값 - 1으로 바꾼다.

또, 만약 중간 인덱스의 값이 M보다 작다면, 최소값을 중간값 + 1로 바꾼다. 그리고 이것을 최솟값이 최댓값보다 작거나 같을 동안만 계속 반복한다.

 

구현 코드

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

public class Section6_8_MyVer {
    int solution(int n, int m, int[] list) {
        int low = 0;
        int high = n - 1;
        int mid = (low + high) / 2;
        Arrays.sort(list);
        while (low <= high) {
            mid = (low + high) / 2;
            if (list[mid] > m)  high = mid - 1;
            else if (list[mid] == m)    break;
            else    low = mid + 1;
        }

        return mid + 1;
    }

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

 

이진탐색의 시간복잡도

O(logn)

배열의 크기에 비하여 실행 시간이 빠르다. -> 대용량 데이터에서 특정 값의 위치를 찾는 데 용이하다.