[이분 검색(Binary Search)] 이분 검색

 

 

설명

 

 

 

 

 

 

 

풀이

 

이 문제를 통해 이분 검색 (Binary Search) 알고리즘에 대해 학습했다.

 

이분 검색은 오름차순이던 내림차순이던 정렬된 상태에서 수행해야 한다.

앞에서부터 쭉 탐색하는 것은 순차 검색이라고 하며, 시간 복잡도는 O(n)이다.

이분 검색의 시간 복잡도는 O(log(n))이다.

 

핵심은 다음과 같다.

• 배열은 오름차순 정렬 되어있다고 가정한다. (Arrays.sort를 이용한다.)
• arr은 데이터가 들어있는 int형 배열이고, m은 찾고자 하는 수이다.
• 두 포인터 변수 lt, rt, 그리고 mid 변수를 이용한다. lt는 왼쪽 인덱스 번호를 나타내며, rt는 오른쪽 인덱스 번호를 나타낸다. mid 변수는 (lt + rt) / 2 이다.
• lt가 rt보다 같거나 작은 동안 반복한다.
  
  • (arr[mid] == m) : 배열의 mid번째 인덱스가 찾고자 하는 값이라면 찾은 것이다. break문으로 멈춘다.
  • (arr[mid] > m) : 배열의 mid번째 인덱스가 찾고자 하는 값보다 크다면 
    • 찾고자 하는 값은 arr[mid]보다 작은 쪽에 있다는 것이다.
    • 그럼, arr[mid] 보다 크거나 같은 쪽은 검색 조건에서 제외한다. 이로 인해 검색 범위가 절반으로 줄어든다.
    • rt 는 mid-1을 가리키면 된다.
  • (arr[mid] < m) : 배열의 mid번째 인덱스가 찾고자 하는 값보다 작다면
    • 찾고자 하는 값은 arr[mid] 보다 큰 쪽에 있다는 것이다.
    • 그럼, arr[mid] 보다 작거나 같은 쪽은 검색 조건에서 제외한다. 이로 인해 검색 범위가 절반으로 줄어든다.
    • lt 는 mid+1을 가리키면 된다.

 

 

 

 

 

코드

 

package inflearn._6_8;

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


public class Main {

    public static int solution(int n, int m, int [] arr) {

        int answer = 0;

        Arrays.sort(arr); // 이분 검색은 정렬이 필수

        int lt = 0, rt = n-1; // 이분 검색을 위한 포인터 변수

        while(lt <= rt) { // 반복 조건
            int mid = (lt + rt) / 2;

            if (arr[mid] == m) { // 찾고자 하는 수인 경우
                answer = mid + 1;
                break;
            }

            // 검색 범위를 좁혀나감
            if (arr[mid] > m) rt = mid - 1;
            else lt = mid + 1;
        }

        return answer;

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int [] arr = new int[n];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(sb.append(solution(n, m, arr)).toString());
        bw.flush();

        bw.close();
        br.close();



    }
}