이진 검색(binary search)

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

 

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

 

 

<예시 문제>

 

설명

임의의 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

 

 

<코드>

import java.util.*;


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

        while(!flag){
            int mid = (lt+rt)/2;
            if(arr[mid] == m) {
                answer= mid+1;
                flag=true;
            }else if(arr[mid]<m) lt = mid;
            else rt = mid;
        }

        return answer;
    }

    public static void main(String[] args) {
      Scanner kb = new Scanner(System.in);
      int n = kb.nextInt();
      int m = kb.nextInt();
      int[] arr = new int[n];

      for(int i=0;i<n;i++){
          arr[i] = kb.nextInt();
      }

        System.out.println(solution(n,m,arr));

    }
}

 

<설명>